尧图网站建设 
题目4. 多重背包问题 I题目描述有N NN种物品和一个容量是V VV的背包。第 i 种物品最多有s i s_isi件每件体积是v i v_ivi价值是w i w_iwi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入格式第一行两个整数N NNV VV用空格隔开分别表示物品种数和背包容积。接下来有N NN行每行三个整数v i v_ivi,w i w_iwi,s i s_isi用空格隔开分别表示第i ii种物品的体积、价值和数量。输出格式输出一个整数表示最大价值。数据范围0 N , V ≤ 100 0 N, V ≤ 1000N,V≤1000 v i , w i , s i ≤ 100 0 v_i, w_i, s_i ≤ 1000vi,wi,si≤100时空限制1s / 64MB输入样例4 5 1 2 3 2 4 1 3 4 3 4 5 2输出样例10思路就是比完全背包多加了个条件ks[i]代码#includebits/stdc.husingnamespacestd;constintN10010;intn,V,v[N],w[N],s[N],f[N][N];intmain(){cinnV;for(inti1;in;i)cinv[i]w[i]s[i];for(inti1;in;i)for(intj0;jV;j)for(intk0;ks[i]k*v[i]j;k)f[i][j]max(f[i][j],f[i-1][j-k*v[i]]k*w[i]);coutf[n][V];return0;}结果 【题解-Acwing】4. 多重背包问题 I
题目4. 多重背包问题 I题目描述有N NN种物品和一个容量是V VV的背包。第 i 种物品最多有s i s_isi件每件体积是v i v_ivi价值是w i w_iwi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入格式第一行两个整数N NNV VV用空格隔开分别表示物品种数和背包容积。接下来有N NN行每行三个整数v i v_ivi,w i w_iwi,s i s_isi用空格隔开分别表示第i ii种物品的体积、价值和数量。输出格式输出一个整数表示最大价值。数据范围0 N , V ≤ 100 0 N, V ≤ 1000N,V≤1000 v i , w i , s i ≤ 100 0 v_i, w_i, s_i ≤ 1000vi,wi,si≤100时空限制1s / 64MB输入样例4 5 1 2 3 2 4 1 3 4 3 4 5 2输出样例10思路就是比完全背包多加了个条件ks[i]代码#includebits/stdc.husingnamespacestd;constintN10010;intn,V,v[N],w[N],s[N],f[N][N];intmain(){cinnV;for(inti1;in;i)cinv[i]w[i]s[i];for(inti1;in;i)for(intj0;jV;j)for(intk0;ks[i]k*v[i]j;k)f[i][j]max(f[i][j],f[i-1][j-k*v[i]]k*w[i]);coutf[n][V];return0;}结果