[C++知识库]杭电2602（C++）

杭电2602

题目

AC代码

#include<iostream>
#include<cmath> 
using namespace std;
int disp[1010];
struct bone
{
	int on;
	int ov;
};

int main()
{
	int n;
	cin>>n;
	int bonenum,bagvec;
	while(n--)
	{
		cin>>bonenum>>bagvec;
		bone bone[bonenum+1];
		for(int i=1;i<=bonenum;i++)
			cin>>bone[i].on;
		for(int i=1;i<=bonenum;i++)
			cin>>bone[i].ov;
		for(int i=0;i<=bagvec;i++)
			disp[i]=0;
		for(int j=1;j<=bonenum;j++)
			for(int i=bagvec;i>=0;i--)
			{
				if(i>=bone[j].ov) 
				{
					disp[i]=max(disp[i],disp[i-bone[j].ov]+bone[j].on);
				}
			}
	cout<<disp[bagvec]<<endl;
	}
	return 0;
}

解题思路

典型01背包问题
可以采用二维数组处理，也可以一维，这里采用一维
无序排序
将当前要或者不要的结果和原来的最优解比较，如果更优则添加

遇到问题

忘记将max的值赋给disp[i]
有时将石头数量和背包此时容量混淆