概述

背包算法是一种典型的递推 dp,其核心要素有三个：

• 背包容量
• 物品重量(体积)
• 物品价值

题目一般要求在背包容量限制下获取最大价值。例如：有 N 件物品，每件物品有对应的重量和价值，在背包空间有限的情况下如何选择物品，是总价值最大。

解题步骤如下：

1. 只有物品 1，背包够大时最大价值就是物品 1 的价值。
2. 拿出物品 2，若背包空间够大则将物品 1、2 全放入背包。若不够大则需做出取舍。
3. 再拿出物品 3，此时有 4 种前置状态：
   • 空包
   • 只含物品 1
   • 只有物品 2
   • 有物品 1、2。
4. 但是，通过第 2 步的计算与取舍，我们已经确定的拿出物品 3 时的唯一条件，此时直接再做取舍即可。

背包问题有 4 中基础类型，分别为：

• 01 背包
• 完全背包
• 分组背包
• 多重背包

在此之上还有针对背包容量升级的二维背包(两个不同的容量限制)、针对物品种类升级的混合背包、有存在依赖关系的背包。

所有背包类型都是01 背包的扩展。

01 背包

在此算法中，我们对每一件物品只有两种操作，即：选择与不选择。

考虑一个表格，其行标 i 表示当前考虑到的物品个数，列标 j 表示当前考虑到的物品容量，最后，这个表格最右下角的值就是我们想要的答案

状态有了，现在的重点是状态转移方程

dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost[i]] + val[i])

完全背包

与 01 背包的区别在于每种物品可以选取无限次，既然可以选择无限次，那么我们一次一次处理就行

状态表示**dp[i][j]**表示 1~i 号商品可以无限拿，容量不超过 j 的最大价值

那么状态转移方程为dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]]+value[i])

空间压缩

// 完全背包+空间压缩

int t, m;
struct Node {
    int a, b;
} node[10005];

// int dp[10005][1000];
int dp[10000005];  // 表示容量c下的最大收益

signed main() {
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> t >> m;

    for (int i = 1; i <= m; i++)
        cin >> node[i].a >> node[i].b;

    for (int i = 1; i <= m; i++)
        for (int c = node[i].a; c <= t; c++) {  // c
            // 这里因为容量c从小往大枚举，所以物品i的次数必然依次增加，不会遗漏
            dp[c] = max(dp[c], dp[c - node[i].a] + node[i].b);
        }

    cout << dp[t];
    return 0;
}