526互联

AcWing 3. 完全背包问题

发布时间 2023-12-04 10:56:56作者: 爬行的蒟蒻

题面：
有 \(N\) 种物品和一个容量是 \(V\) 的背包，每种物品都有无限件可用。
第 \(i\) 种物品的体积是 \(v_i\) ，价值是 \(w_i\) 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

原题链接：3. 完全背包问题 - AcWing

根据01背包的思路扩展到完全背包：

  1. 01背包：建立集合，对于第 \(i\) 种物品来说，有 选/不选 两种选择；
  2. 完全背包：建立集合，对于第 \(i\) 种物品来说，有 选0件（不选）/选1件/选2件/……/选k件/……
    共 \(v/v[i]+1\) 种选择。
  • 完全背包-状态转移方程：\(F(i,j)=max(F(i-1,j),F(i,j-v)+w);\)
  • 推导过程：
    • 01背包-状态转移方程：\(F(i, j) = max(F(i-1, j), F(i-1, j-Vi) + Wi)\) \(j≥Vi\)；
    • 完全背包-朴素方程：\(F(i, j) = max(F(i-1, j), F(i-1, j-Vi) + Wi, F(i-1, j-2×Vi) + 2×Wi...)\) \(j≥Vi\)；
    • 等价变形：\(F(i, j-v_i) = max(F(i-1, j-v_i), F(i-1, 2×j-Vi) + Wi, F(i-1, j-3×Vi) + 2×Wi...)+w\) \(j≥Vi\)；
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int v[N], w[N];
int f[N][N];

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			f[i][j] = f[i - 1][j];
			if (j >= v[i])
				f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
		}
	}
	cout << f[n][m];
}

二次优化降维

  1. 01背包优化：从大到小枚举体积；
    ①确保在计算 \(f[j]\) 时，\(f[j-v[i]]\) 已经被更新过：
    ②保证每个物品仅被添加一次。
  2. 完全背包优化：从小到大枚举体积；
    因为当背包容积较小时，右侧集合不一定存在。
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int v[N], w[N], f[N];

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];
	for (int i = 1; i <= n; i++)
	    for (int j = v[i]; j <= m; j++)
			f[j] = max(f[j], f[j - v[i]] + w[i]);
	cout << f[m];
}