首页 > 代码库 > 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活（复习多重背包）
悼念512汶川大地震遇难同胞——珍惜现在，感恩生活（复习多重背包）
悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
传送门
【题目大意】
在资金一定的情况下，给出救难用的每袋大米的重量，价格，袋数。求购买大米的最终重量。
【思路】多重背包。
【复习】多重背包特点。
题目
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
【code】
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int t,mon,k,w[102],pri[102],f[102],cnt[102]; int main() { scanf("%d",&t); while(t--) { memset(f,0,sizeof(f)); scanf("%d%d",&mon,&k); for(int i=1;i<=k;i++) scanf("%d%d%d",&pri[i],&w[i],&cnt[i]); for(int i=1;i<=k;i++) { for(int j=mon;j>=pri[i];j--) { for(int h=0;h<=cnt[i];h++) { if(j-h*pri[i]<0)break; f[j]=max(f[j],f[j-h*pri[i]]+h*w[i]); } } } printf("%d\n",f[mon]); } return 0; }
悼念512汶川大地震遇难同胞——珍惜现在，感恩生活（复习多重背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。