汉扬编程 编程大纲 初级编程C++题:11H1331: 混合背包

初级编程C++题:11H1331: 混合背包

初级编程C++题:11H1331: 混合背包

时间限制: 1 Sec 内存限制: 128 MB

初级编程C++题:11H1331: 混合背包

初级编程C++题:11H1331: 混合背包

题目描述

一个旅行者有一个最多能用V公斤的背包,现在有N件物品,它们的重量分别是W1,W2,….Wn,它们的价值分别为C1,C2,..Cn有的物品只可以取一次(01背包)有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

输入

第一行:两个整数,V(背包容量,V<=200),N(物品数量,N<=30);

第2..N+1行:每行三个整数Wi,Ci,Pi,前两个整数分别表示每个物品的重量,价值,第三个整数若为0,则说明此物品可以购买无数件,若为其他数字,则为此物品可购买的最多件数(Pi)

输出

仅一行,一个数,表示最大总价值。

样例输入

10 32 1 03 3 14 5 4样例输出

11提示

选经一件物品1件,第三件物品2件

答案:

#include<bits/stdc++.h>using namespace std;int m,n;int w[31],c[31],p[31];int f[201];int main(){ cin>>m>>n; for(int i=1;i<=n;i++) cin>>w[i]>>c[i]>>p[i]; for(int i=1;i<=n;i++){ if(p[i]==0) { for(int j=w[i];j<=m;j++) f[j]=max(f[j],f[j-w[i]]+c[i]); } else { for(int j=1;j<=p[i];j++) for(int k=m;k>=w[i];k–) f[k]=max(f[k],f[k-w[i]]+c[i]); } } cout<<f[m]; return 0;}

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/5855.html

很多学C语言的人不知道的事儿,小数是如何存储的?二进制白学了

易语言做的计算器精度问题

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部