首页 > 代码库 > 杭电2602 Bone Collector 【01背包】
杭电2602 Bone Collector 【01背包】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2602
解题思路：给出一个容量为V的包，以及n个物品，每一个物品的耗费的费用记作c[i]（即该物品的体积），每一个物品的价值记作w[i]，
我们用 f[v]来表示一个容量为v的包的总价值，这样最后我们只需要输出f[V]就能得出结果
则对于第i个物品，它可以放入背包，此时背包的容量变为v-c[i],背包的总价值变为f[v-c[i]]+w[i],
它也可以不放入背包，此时背包的容量还是v,背包的总价值不变，仍为f[v]
所以我们只需要取这两种情况中的最大值即可
f[v]=max(f(v),f(v-c[i])+w[i]);
#include<stdio.h>#include<string.h>int max(int a,int b){ if(a>b) return a; else return b;}int main(){ int ncase,n,V; int i,v; int c[1005],w[1005]; long int f[1005]; while(scanf("%d",&ncase)!=EOF) { while(ncase--) { for(i=0;i<1005;i++) f[i]=0; scanf("%d %d",&n,&V); for(i=0;i<n;i++) scanf("%d",&w[i]); //每一个的价值 for(i=0;i<n;i++) scanf("%d",&c[i]);//每一个的体积 for(i=0;i<n;i++) { for(v=V;v>=c[i];v--) { f[v]=max(f[v],f[v-c[i]]+w[i]); } } printf("%ld\n",f[V]); } }}
杭电2602 Bone Collector 【01背包】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。