宜昌市住房和城乡建设厅网站,小程序上线需要多少钱,it教育培训机构排名,管理咨询公司一般是做什么的题目描述
有N种物品和一个容量是V的背包。 第i种物品最多有si件#xff0c;每件体积是vi#xff0c;价值是wi。 求解将哪些物品装入背包#xff0c;可使物品体积总和不超过背包容量#xff0c;且价值总和最大。 输出最大价值。
输入
第一行两个整数#xff0c;N#x…题目描述
有N种物品和一个容量是V的背包。 第i种物品最多有si件每件体积是vi价值是wi。 求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入
第一行两个整数NV用空格隔开分别表示物品种数和背包容积。 接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。
0N,V≤100 0vi,wi,si≤100 输出
输出一个整数代表最大价值。
样例输入
4 10
3 2 2
4 3 2
2 2 1
5 3 4
样例输出
8 代码如下
只比01背包多了一点
#includebits/stdc.h
using namespace std;
long long n,maxv,v1,w1,s1,v[10001],w[10001];
int main(){cinnmaxv;long long k0;for(int i1;in;i){cinw1v1s1;for(int j1;js1;j){k;v[k]v1;w[k]w1;}}for(int i1;ik;i){for(int jmaxv;jw[i];j--){dp[j]max(dp[j],v[i]dp[j-w[i]]);}}coutdp[maxv];return 0;
}
7~14行把多重背包转成01背包
