背包问题

# 题型
## 01 背包 问题
## 01 背包特殊形式: 体积就是价值式背包
## 完全背包 问题
## 多重背包 问题
## 分组背包 问题

markmap##h300

01背包 问题

Warning

01背包问题:
有一个背包的容积为V，有N个物品，每个物品的体积为v[i]，权重为w[i]，每个物品只能取1次放入背包中，背包所有物品权重和最大是多少?

---

体积就是价值式 01背包

Warning

典型题目:

有一个箱子容量为 $V$，同时有 $n$ 个物品，每个物品有一个体积。

现在从 $n$ 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

变式:

完全背包 问题

Warning

完全背包:
有一个背包的容积为V，有N个物品，每个物品的体积为v[i]，权重为w[i]，每个物品可以取无限次放入背包中，背包所有物品权重和最大是多少?

01背包问题和完全背包问题的区别就在于，每个物品取的最大次数是1次还是无限次

状态

Tip

依旧是 dp(i, j)

Important

其中 i 是 尝试放入第i个物品, j 是 放入第i个物品后的背包容量

状态转移方程

推导

我们知道 01背包问题 的状态转移方程是

##container##
$dp(i, j) = max(dp(i - 1, j), dp(i - 1, j - v[i]) + w[i])$

意思是 背包容量为j时, 尝试放入物品i后 数组dp[i][j]处最优值(权重最大值), 是
数组dp[i - 1][j]处最优值(权重最大值) [不放]
数组dp[i - 1][j - w[i]]处最优值(权重最大值) [放]
的最大值

那么 通过 01背包问题不同的是这里我们每种物品都可以使用无数次， 而01背包问题则将每个物品的使用限定在了一次 这个区别, 我们可以想到以下代码:

for(int i = 1; i <= n; i++)
{
        for(int j = 0; j <= m; j++)
        {
            for(int k = 0; k <= j/v[i]; k++)
                dp[i][j] = max( dp[i-1][j], dp[i-1][j - k*v[i]] + k*w[i] );
        }
}

C++

即 在 第 i 个位置, 尝试将 物品i 放入背包 0 ~ $j/v[i]$ 次 (最里层 for : k)

即

##container##
$dp(i, j) = max(dp(i - 1, j), dp(i - 1, j - k * v[i]) + k * w[i]),其中k=1,...,j/v[i]$

如果你问什么加个尝试多次就可以?

那就是因为 它是和dp[i-1][j]比较的, 而dp[i-1][j]绝对是最优值, 所以不用担心值被非最优的覆盖.

当然, 上面的只是一种暴力的的解法 时间复杂度为 O(N^3), 下面才是推导的正文

状态压缩

对于

##container##
$dp(i, j) = max(dp(i - 1, j), dp(i - 1, j - k * v[i]) + k * w[i])$

我们将其展开有

##container##
$dp(i, j) = max(dp(i - 1, j), dp(i - 1, j - 1 * v[i]) + 1 * w[i]), dp(i - 1, j - 2 * v[i]) + 2 * w[i]), ...$

对于 dp(i, j - v[i]) 有

##container##
$dp(i, j - v[i]) = max(dp(i - 1, j - v[i]), dp(i - 1, j - 2 * v[i]) + 1 * w[i], dp(i - 1, j - 3 * v[i]) + 2 * w[i], ...)$

注意: 此处的 dp(i, j - v[i]) 的 j - v[i] 是小于 j 的, 如果是从左往右遍历计算的话, 那么实际上结果我们是已经知道的

亦有

$dp(i, j) = max(dp(i - 1, j), dp(i - 1, j - 1 * v[i]) + 1 * w[i], dp(i - 1, j - 2 * v[i]) + 2 * w[i], ...)$

$= max(dp(i - 1, j), max(dp(i - 1, j - 1 * v[i]) + 1 * w[i], dp(i - 1, j - 2 * v[i]) + 2 * w[i], ...))$

$= max(dp(i - 1, j), dp(i, j - v[i]) + w[i])$

对比一下: 是不是很像?

01背包	完全背包
$dp(i, j) = max(dp(i - 1, j), dp(i - 1, j - v[i]) + w[i])$	$dp(i, j) = max(dp(i - 1, j), dp(i, j - v[i]) + w[i])$

他们只是相差一个 1 而已哦~ max的时候~, 如果直接给你这个方程, 你是不是不敢相信?

但, 推导过后, 它就是这么妙~

多重背包 问题

混合背包 问题

题目: P1833 樱花

描述:

在一个容积为 $V$ 的背包中, 可以放下 $n$ 种物品, 第 $i$ 种物品 (其价值为 $W_i$ ) 可以放 $P_i$ 次, 其中 $P_i=0$ 意味着可以放无数次

求: 容积不超过 $V$ 的情况下, 背包可以放下物品的最大价值.

下面给一个状态压缩后的代码:

int t, n;
scanf("%d %d", &t, &n);

int t_arr[10001], c_arr[10001], p_arr[10001] = { 0 };
for (int i = 0; i < n; ++i) {
    scanf("%d %d %d", t_arr + i, c_arr + i, p_arr + i);
}

int dp[10001] = { 0 };
for (int i = 0; i < n; ++i) {
    if (p_arr[i] == 0) {
        // 完全背包
        for (int j = t_arr[i]; j <= t; ++j)
            dp[j] = max(dp[j], dp[j - t_arr[i]] + c_arr[i]);
    }
    else {
        // 01背包, 多重背包
        for (int j = 1; j <= p_arr[i]; ++j)
            for (int k = t; k >= t_arr[i]; --k)
                dp[k] = max(dp[k], dp[k - t_arr[i]] + c_arr[i]);
    }
}

C++