HDU 2602 Bone Collector【01背包入门题】

开发技术 作者: 2024-06-20 23:50:01
Bone CollectorTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 52370Accepted Submission(s): 22079Pr

Bone Collector

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)@H_301_7@ Total Submission(s): 52370    Accepted Submission(s): 22079@H_301_7@

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 …@H_301_7@ 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 ?@H_301_7@

@H_301_7@
 

Input
The first line contain a integer T,the number of cases.@H_301_7@ 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 2@H_301_40@31).
 

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
 
原题链接:http://acm.split.hdu.edu.cn/showproblem.PHP?pid=2602

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 开!

@H_301_7@

优化成1维的:

伪代码:

for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]};
@H_301_7@ f[v] : 体积为v的背包的最大价值。

@H_301_7@

参考博客:http://www.wutianqi.com/?p=539

http://www.cnblogs.com/jiangjun/archive/2012/05/08/2489590.html@H_301_7@

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; }
@H_301_7@

@H_301_7@

优化成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("%d\n",dp[V]); } return 0; }
@H_301_7@ @H_301_7@

尊重原创,转载请注明出处:http://blog.csdn.net/hurmishine@H_301_7@

@H_301_7@

@H_301_7@

@H_301_7@

@H_301_7@

原创声明
本站部分文章基于互联网的整理,我们会把真正“有用/优质”的文章整理提供给各位开发者。本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
本文链接:http://www.jiecseo.com/news/show_30647.html