HDU 2602 Bone Collector【01背包入门题】
发布时间：2020-12-13 21:17:21 所属栏目：PHP教程 来源：网络整理
导读：Bone Collector Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 52370Accepted Submission(s): 22079 Problem Description Many years ago,in Teddy’s hometown there was a man who was called
Bone CollectorTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 52370 Accepted Submission(s): 22079
Problem Description
Many years ago,in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones,such as dog’s,cow’s,also he went to the grave …
The bone collector had a big bag with a volume of V,and along his trip of collecting there are a lot of bones,obviously,different bone has different value and different volume,now given the each bone’s value along his trip,can you calculate out the maximum of the total value the bone collector can get ?
Input
The first line contain a integer T,the number of cases.
Followed by T cases,each case three lines,the first line contain two integer N,V,(N <= 1000,V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output
One integer per line representing the maximum of the total value (this number will be less than 231).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
Author
Teddy
Source
HDU 1st “Vegetable-Birds Cup” Programming
Open Contest
Recommend
lcy
01背包入门题： 转态转移方程： f[i][v] = max ( f[i⑴][v],f[i⑴][v-c[i] ]+w[i] ) f[i][v]:前 i 件物品放入容量为v的背包取得最大价值。 c[i]: 第 i 件物品的体积。 w[i] :第 i 件物品的体积价值。 注意：输入数据的时候数组下标要从 1 开！
优化成1维的： 伪代码： for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
f[v] : 体积为v的背包的最大价值。
参考博客：http://www.wutianqi.com/?p=539 http://www.cnblogs.com/jiangjun/archive/2012/05/08/2489590.html 2维AC代码： #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1005;
int v[maxn];
int val[maxn];
int dp[maxn][maxn];
int main()
{
int T,n,V;
ios::sync_with_stdio(false);
cin.tie(0);
//freopen("data/2602.txt","r",stdin);
cin>>T;
while(T--)
{
cin>>n>>V;
memset(dp,sizeof(dp));
//memset(v,sizeof(v));
//memset(val,sizeof(val));
for(int i=1;i<=n;i++)
cin>>val[i];
for(int i=1;i<=n;i++)
cin>>v[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=V;j++)
{
if(j>=v[i])
dp[i][j]=max(dp[i⑴][j],dp[i⑴][j-v[i]]+val[i]);
else
dp[i][j]=dp[i⑴][j];
}
}
cout<<dp[n][V]<<endl;
}
return 0;
}
优化成1维AC代码：#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,v[1005],val[1005],dp[1005];
scanf("%d%d",&n,&V);
int i,j,k;
for(i=0; i<n; i++)
scanf("%d",&val[i]);
for(i=0; i<n; i++)
scanf("%d",&v[i]);
memset(dp,sizeof(dp));
for(i=0; i<n; i++)
for(j=V; j>=v[i]; j--)
dp[j]=max(dp[j],dp[j-v[i]]+val[i]);
printf("%dn",dp[V]);
}
return 0;
}
尊重原创，转载请注明出处：http://blog.csdn.net/hurmishine
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
