HDOJ:2602

题目大意:许多年前,在泰迪的家乡,有一个人被称为"骨收藏家"。这个人喜欢收集各种骨头,如狗的,牛的,他也去了坟墓。
骨收藏家有一个大包,有一卷V,在他的收集之旅有很多骨头,显然,不同的骨头有不同的价值和不同的体积,现在考虑到每块骨头的价值,他的行程,你能算出骨收藏家可以得到的总价值的最大值吗?

解题思路:

0 1 2 3 4 5 6 7 8 9 10
1 5 0 0 0 0 0 1 1 1 1 1 1
2 4 0 0 0 0 2 2 2 2 2 3 3
3 3 0 0 0 3 3 3 3 5 5 5 5
4 2 0 0 4 4 4 7 7 7 7 9 9
5 1 0 5 5 9 9 9 12 12 12 12 14

状态转移方程:dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

代码:

#include<bits/stdc++.h>
using namespace std;
int dp[100][100];
int v[1001];
int w[1001];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		memset(dp,0,sizeof(dp));
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		cin>>w[i];
		for(int i=1;i<=n;i++)
		cin>>v[i];
		for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
	    if(j>=v[i])
		dp[i][j]= max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
		else
		dp[i][j]=dp[i-1][j];
			}
		cout<<dp[n][m]<<endl;
	}
	return 0;
}

上一篇:Bzoj2442:修剪草坪


下一篇:HDOJ 1421搬寝室