load.cpp

还挺好的

/*
*	For Algrithm ShiYan3
*	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 *w;
int n=0;
int c=0;
int **m;

void makeM()
{
	//jIndex表示在m矩阵当前行理论上可以分配的初始位置,w[n-1]-1为下标！
	for(int lie=0;lie<w[n];lie++)
	{
		m[n][lie] = 0;
	}
	for(int lie=w[n];lie<=c;lie++)
	{
		m[n][lie] = w[n];
	}

	//后边的算法只要根据前边.
	for(int line=n-1;line>0;line--)
	{
		for(int lie=1;lie<w[line];lie++)
		{
			m[line][lie]=m[line+1][lie];
		}
		for(int lie=w[line];lie<=c;lie++)
		{
			m[line][lie]=max(m[line+1][lie],(m[line+1][lie-w[line]]+w[line]));
		}
	}	
}

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>>c;
	w = new int[n+1];
	for(int i=1;i<=n;i++)
	{
		fileIn>>w[i];
	}
	fileIn.close();

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

	//从m[][]中提取出最优解放入x数组
	int *x= new int[n+1];
	x[0]=0;
	int tmp=c;
	for(int line=1;line<n;line++)
	{
		if(m[line][tmp]==m[line+1][tmp])
		{
			x[line]=0;
		}else
		{
			x[line]=1;
			tmp = tmp - w[line];
		}
	}
	if(m[n][tmp]==0)
	{
		x[n]=0;
	}else
	{
		x[n]=1;
	}

	//输出解到文件
	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;
	for(int i=1;i<=n;i++)
	{
		fileOut<<x[i]<<" ";
	}
	fileOut.close();
}