多重背包问题
多重背包问题
来源
https://www.acwing.com/problem/content/4/
Description
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
Input
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
Output
输出一个整数，表示最大价值。
数据范围
0Sample Input
4 5
1 2 3
2 4 1
3 4 3
4 5 2
Sample Output
10
分析问题:
-
多重背包问题:每种物品可以取s[i]次
-
多重背包问题的分析同样可以借助于01背包问题的,不同的点就是需要增加k维以枚举物品的取用次数:
- 状态表达式:dp[j]表示j体积下的物品最大价值
- 转态转移方程:dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i])
- 初始化:dp[0]=0
#include#include #include #include #include #define INF 0x3f3f3f3f using namespace std; const int N=1e3; int dp[N+10],w[N],v[N],s[N]; //dp[i]在i体积下的最大价值 int main() { int n,m; while(~scanf("%d %d",&n,&m)){ memset(dp,0,sizeof dp); for(int i=1;i<=n;i++){ scanf("%d %d %d",&w[i],&v[i],&s[i]); } for(int i=1;i<=n;i++){ for(int j=m;j>=w[i];j--){ //基于0/1算法改进,所以这里同样需要从大到小遍历 for(int k=1;k<=s[i]&&k*w[i]<=j;k++){ //需要保证物品的个数和对应的总体积之和小于m //cout << k*v[i] << endl; dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]); } } } cout << dp[m] << endl; } }