首页 > 代码库 > hduoj2602Bone Collector
hduoj2602Bone Collector
<marquee width="600"></marquee> |
Bone CollectorTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) 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
Sample Output
翻译:有一人爱收集骨头,每个骨头有一个价值和重量,他有一个背包,容量为V,问他装得最大价值量是多少?(经典的01背包问题) 重点:01背包、动态规划 难点:动态方程的书写 #include<iostream> #include<cstdio> #include<cstring> using namespace std; int main() { int T,n,v,i,j,dp[1100],a[1100],b[1100];//a[1100]是价值,b[1100]是重量; cin>>T; while(T--) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(dp,0,sizeof(dp)); cin>>n>>v;//n是骨头个数,V是背包容量 for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) scanf("%d",&b[i]); for(i=1;i<=n;i++) for(j=v;j>=b[i];j--) { if(dp[j]<dp[j-b[i]]+a[i]) dp[j]=dp[j-b[i]]+a[i]; } printf("%d\n",dp[v]); } return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。