bag_3.cpp

这是经典的背包问题

#include<iostream.h>
//////////////////////////////////////////////////////////////////////////
//背包三
//有价值分别为x1 x2 x3  x4  x5...xt (t<100 && xi(int))金属,
//体积为y1 y2  y3  y4...yt (yi(int))个单位且金属不可以分割
//有一个背包大小为t个单位(t<100)
//求背包能装的金属的最大的价值
//动态规划法
////////////////////////////////////////////////////////////////////////////////
struct metal
{
	int value;
	int volume;
};

metal metal_group[100];

int pp[110][110];//x个单位体积的背包在前y个金属中可以获得的最大价值pp[x][y]

int cal_metal_value();

int cal_metal_value()
{
	int n,t;
	cout<<"put in the number of kind of the metal and the total volume"<<endl;
    cin>>n>>t;
	cout<<"put in each metal's value and volume"<<endl;
	for (int r=1;r<=n;r++)
	    cin>>metal_group[r].value>>metal_group[r].volume;

    for(int i=1;i<=t;i++)
	   for(int j=1;j<=n;j++)
		   if((metal_group[j].volume<=i)
			   &&metal_group[j].value+pp[i-metal_group[j].volume][j-1]>pp[i][j-1])
			   pp[i][j]=metal_group[j].value+pp[i-metal_group[j].volume][j-1];
		   else
			   pp[i][j]=pp[i][j-1];
	return pp[t][n];
}


void main()
{
	cal_metal_value();
}