最小重量机器设计问题.cpp

王晓东算法设计与分析课后一些题目的源码。vc下全都编译通过。且在学校网站上提交通过。是学习算法较好的参考资料

#include <iostream>
using namespace std;

int nm,mm,cm;    
int pc[101][101]; 
int pw[101][101]; 
int sumc,sumw,bestw,bestc;    

int bak(int d)
{
	if(d>nm)
	{
		if( (bestw == -1 || sumw < bestw) && sumc <= cm )
		{
			bestw=sumw;
			bestc=sumc;
		}
	}
	else
	{
		for(int j=1;j<=mm;j++)
		{
			sumw+=pw[d][j];
			sumc+=pc[d][j];
			if(cm >=sumc && (sumw < bestw || bestw == -1) )
			bak(d+1);
			sumw-=pw[d][j];
			sumc-=pc[d][j];
		}
	}
	return 0;
}
int main()
{
	int i,j;
	sumc=sumw=0;
	bestw=-1;
	bestc=0;
	while(cin>>nm>>mm>>cm)
	{
		for(i=1;i<=nm;i++)
		{
			for(j=1;j<=mm;j++)
			{
				cin>>pc[i][j];
			}
		}
		for(i=1;i<=nm;i++)
		{
			for(j=1;j<=mm;j++)
			{
				cin>>pw[i][j];
			}
		}
		bak(1);
		if(bestw==-1) cout << "No Solution!" << endl;
        else cout << bestw << endl;
        bestw = -1; 
	}
	system("pause");
	//return 0;
}