change.cpp

还挺好的

/*
*	For Algrithm ShiYan2
*	Author:[e-mail]
*	No:20053424
*	Date:2008/04/22
*/
#include <iostream>
#include <string>
#include <fstream>
#include <math.h>
#define INPUT_FILE "input.txt"
#define OUTPUT_FILE "output.txt"
using namespace std; 
int *t;
int n=0;
int iniJ=0;
int **c;

void makeC()
{	
	//置列0全为0
	for(int line=1;line<=n;line++)
	{
		c[line][0]=0;
	}

	//按列顺序执行！
	for(int lie=1;lie<=iniJ;lie++)
	{	
		if(lie%t[1]==0)
		{
			c[1][lie]=lie/t[1];
		}else
		{
			c[1][lie]=1000;
		}
		//列中按行执行！
		for(int line=2;line<=n;line++)
		{
			if(t[line]>lie)
			{
				c[line][lie]=c[line-1][lie];
			}else
			{
				c[line][lie]=min(c[line-1][lie],c[line][lie-t[line]]+1);
			}
		}
	}
}

int main()
{
	//打开输入文件赋初值
	ifstream fileIn;
	fileIn.open(INPUT_FILE);
	if(fileIn==0)
	{
		cout<<"Please check the input file named:"<<INPUT_FILE<<endl;
		exit(0);
	}else
	{
		cout<<"The file have been read:"<<INPUT_FILE<<endl;
	}
	fileIn>>n;
	t = new int[n+1];
	for(int i=1;i<=n;i++)
	{
		fileIn>>t[i];
	}
	fileIn>>iniJ;
	fileIn.close();

	//为m[][]分配空间
	c =new int*[n+1];
	for(int i=0;i<n+1;i++)
	{
		c[i] = new int[iniJ+1];
	}
	
	//计算m[][]来存储m(i,j)的相应值
	makeC();

	//输出解到文件
	ofstream fileOut;
	fileOut.open(OUTPUT_FILE);
	if(fileOut==0)
	{
		cout<<"The result cannot be output to file: "<<OUTPUT_FILE<<"Please Check!"<<endl;
		exit(0);
	}else
	{
		cout<<"The result have been saved to file: "<<OUTPUT_FILE<<endl;
	}
	fileOut<<"Author:[e-mail]"<<endl;
	int mini=c[1][iniJ];
	for(int line=2;line<=n;line++)
	{
		if(mini>c[line][iniJ])
		{
				mini=c[line][iniJ];			
		}
	}
	fileOut<<mini<<endl;
	fileOut.close();
	for(int line=1;line<=n;line++)
	{
		for(int lie=0;lie<=iniJ;lie++)
			cout<<c[line][lie]<<" ";
		cout<<endl;
	}
}