多重背包算法笔记

每种物品数量有限制的完全背包问题。

问题描述

在完全背包的基础上,每种物品有数量限制。最多有\(n[i]\)个.

思路分析

思路一

多重背包问题的思路跟完全背包的思路非常类似,只是\(k\)的取值是有限制的,因为每件物品的数量是有限制,状态转移方程为: \[ dp[i][j] = max\{dp[i - 1][j - k * w[i]] + v[i], dp[i-1][j] \}\ \ (0≤k≤ n[i]且k*w[i]≤j) \] 思路二

转化为01背包去解。比如1号物品\((w,v)=(2,1), n=2\),可以把它看作有两个\((w,v)=(2,1)\)的物品。

数量 重量 价值
0 0 0
1 5 1
2 4 2
1 3 3
2 2 4
1 1 5

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;

int main()
{
int C = 15;
int n = 5;
int w[6] = { 0,5,4,3,2,1 };
int v[6] = { 0,1,2,3,4,5 };
int num[6] = { 0,1,2,1,2,1 };

vector<int> dp(C + 1);
for (int i = 1; i <= n; i++) //把前两个循环看成一个循环,就拆开了
for (int k = 1; k <= num[i]; k++)
for (int j = C; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[C] << endl;
system("pause");
return 0;
}