首页 > 代码库 > hdu 2602 Bone Collector （01 背包基础）
hdu 2602 Bone Collector （01 背包基础）
http://acm.hdu.edu.cn/showproblem.php?pid=2602
题意 ： n个骨头 m的容量
给出n个骨头的 value 和 volume
求m能容纳的最大价值
思路 ：
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int main(){ int n,m,t; int v[1000+10],w[1000+10]; int dp[1000+10]; int i,j,k; scanf("%d",&t); while(t--) { memset(dp,-1,sizeof(dp)); dp[0]=0; int ans=0; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&v[i]); for(i=1;i<=n;i++) scanf("%d",&w[i]); for(i=1;i<=n;i++) { for(j=m;j>=w[i];j--) { if(dp[j-w[i]]!=-1) { dp[j]=max(dp[j],dp[j-w[i]]+v[i]); if(ans<dp[j]) ans=dp[j]; } } } printf("%d\n",ans); } return 0;}
hdu 2602 Bone Collector （01 背包基础）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。