背包问题

AcWing 2. $01$背包问题

已知 $N$ 件物品和一个容量是 $M$ 的背包。每件物品只能使用一次。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。求最大价值。

状态表示：f[i][j]
    集合：从第 1 - i 件物品中选，总体积不超过 j 的方案的集合
    属性：Max 价值的最大值
状态计算：1. 不选第 i 个物品，则 f[i][j] = f[i - 1][j]
          2. 选第 i 个物品，则 f[i][j] = f[i - 1][j - v[i]] + w[i]
          综上，f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])

优化：将数组 f 降为一维
      有状态转移方程 f[j] = max(f[j], f[j - v[i]] + w[i])
      因为 f[i - 1][j - v[i]] + w[i] 中的 i - 1，所以 j 应从大到小循环

目标状态：f[m]

Code

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N], f[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);

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

    printf("%d\n", f[m]);

    return 0;
}

AcWing 3. 完全背包问题

已知 $N$ 种物品和一个容量是 $M$ 的背包。每种物品都有无限件可用。第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。求最大价值。

状态表示：f[i][j]
    集合：从第 1 - i 件物品中选，总体积不超过 j 的方案的集合
    属性：Max 价值的最大值
状态计算：考虑第 i 个物品选几个，分类
          选 0 个，则价值为 f[i - 1][j]
          选 1 个，则价值为 f[i - 1][j - v[i]] + w[i]
          ...
          选 s 个，s 为满足 v[i] * s <= j 的最大值，则价值为 f[i - 1][j - v[i] * s] + w[i] * s
          因此，f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], f[i - 1][j - v[i] * 2] + w[i] * 2, ... , f[i - 1][j - v[i] * s] + w[i] * s)

优化：f[i][j - v[i]] = max(f[i - 1][j - v[i]], f[i - 1][j - v[i] * 2] + w[i], ... , f[i - 1][j - v[i] * s] + w[i] * (s - 1))
      因此，有 f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])
      进一步降维优化，有 f[j] = max(f[j], f[j - v[i]] + w[i])
      因为 f[i][j - v[i]] + w[i] 中的 i，所以 j 应从小到大循环

目标状态：f[m]

Code

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &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]);

    printf("%d\n", f[m]);

    return 0;
}

中间可能会有些题跳过去没整理，以后会加上！！！

中间可能会有些题跳过去没整理，以后会加上！！！

以后还会继续更新！！！

以后还会继续更新！！！