企业官网建设流程全解析

题目：4. 多重背包问题 I

题目描述

有N NN种物品和一个容量是V VV的背包。

第 i 种物品最多有s i s_isi​件，每件体积是v i v_ivi​，价值是w i w_iwi​。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，N NN，V VV，用空格隔开，分别表示物品种数和背包容积。

接下来有N NN行，每行三个整数v i v_ivi​,w i w_iwi​,s i s_isi​，用空格隔开，分别表示第i ii种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N , V ≤ 100 0 < N, V ≤ 1000<N,V≤100

0 < v i , w i , s i ≤ 100 0 < v_i, w_i, s_i ≤ 1000<vi​,wi​,si​≤100

时空限制

1s / 64MB

输入样例

4 5 1 2 3 2 4 1 3 4 3 4 5 2

输出样例

10

思路

就是比完全背包多加了个条件k<=s[i]

代码

#include<bits/stdc++.h>usingnamespacestd;constintN=100+10;intn,V,v[N],w[N],s[N],f[N][N];intmain(){cin>>n>>V;for(inti=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];for(inti=1;i<=n;i++)for(intj=0;j<=V;j++)for(intk=0;k<=s[i]&&k*v[i]<=j;k++)f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);cout<<f[n][V];return0;}

结果