hdu 2602 Bone Collector 01双肩包

hdu 2602 Bone Collector 01背包

经典的01背包问题，去年集训的时候没有做出来的题目，原来是如此简单。。。

思路：

dp[i+1][j]代表选前i个骨头总容量不超过j的最大价值，所以可得到状态方程

|dp[i+1][j] = dp[i][j](vol[i] > j当前i的容量大于j)  |

|dp[i+1][j] = max{dp[i][j],dp[i][j-vol[i]]+val[i]}|(当前i的容量小于j，只存在装与不装第i个骨头，所以选择最大的即可)

贴代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<algorithm>

using namespace std;
int dp[1005][1005];
int vol[1005];
int val[1005];
int main()
{
	int T,v,i,j,n;
	cin >> T;
	while(T--)
	{
		cin >> n >> v;
		for(i=1; i<=n; i++)
			cin >> val[i];
		for(i=1; i<=n; i++)
			cin >> vol[i];
		for(i=0; i<=v; i++)
			dp[1][i] = 0;
		for(i=1; i<=n; i++)
		{
			for(j=0; j<=v; j++)
			{
				if(j < vol[i])
					dp[i+1][j] = dp[i][j];
				else
					dp[i+1][j] = max(dp[i][j],dp[i][j-vol[i]]+val[i]);
			}
		}
		cout << dp[n+1][v] << endl;
	} 
	return 0;
}