零. dp 分析

• 状态表示
  • 集合：所有…的集合
    • 条件：边界、前几个、后几个、体积小于…、时间小于…等（集合的设计带来的一些边界条件）
  • 属性：max、min ......（状态表示了这个集合的什么值？与状态转移相区别）
• 状态计算（状态之间的关系）：主要看最后一步到当前状态的状态转移。

一. 二维 dp

一.1. 状态设计

f[i][j] 表示前 i 个物品中，背包容量为 j 时，能得到的最大值。

一.2. 状态计算

f[i][j] = max(f[i-1][j], f[i-1][j-vol[i]] + val[i])

即，f[i][j] 来自下面两个状态的最大值：

• 不选第 i 个物品。前 i - 1 个物品，背包容量为 j 时，可以选取的物品最大值
• 选第 i 个物品。前 i - 1 个物品，背包容量为 j - vol[i] 时，可以选取的物品最大值与第 i 个物品价值的和。

一.3. 时间复杂度

状态空间 $O(n^{2})$，约为 $10^6$

一.4. 代码

注意：

• f[0][*]留作边界
• 当 j >= vol[i] 时就要考虑选取第 i 个物品，若等于时不考虑不符合题意，属于漏掉了空间恰好只能放第 i 个物品时候的情况。

#include<iostream>

#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rrep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rrep_gt(i, a, b) for(int i = (b); i > (a); -- i)

using namespace std;

const int N = 1e3 + 5;

int val[N], vol[N];
int res[N][N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 0, container = 0;
    cin >> n >> container;
    _rep_le(i, 1, n) {
        cin >> vol[i] >> val[i];
    }

    res[0][0] = 0;
    _rep_le(i, 1, n) {
        _rep_le(j, 1, container) {
            res[i][j] = res[i - 1][j];
            if(j >= vol[i]) {
                int temp = res[i - 1][j - vol[i]] + val[i];
                res[i][j] = res[i][j] > (temp) ? res[i][j] : temp;
            } 
        }
    }

    cout << res[n][container] << endl;

    return 0;
}

二. 优化

二.1. 空间压缩-分析

• res[i][j] 只和 res[i-1][...] 有关系，故 res 数组可以压缩为一维的，但遍历过程并不能减少。
• 在求 res[i][j] 时候要用到 res[i-1][range] 其中 range 属于 [0, j-1]，因此减少一维后，在内层遍历时，为了能够正确使用 res[i-1][range] 内层循环应从后向前遍历
• 从后向前遍历，内层可以不用 if 判断 j >= vol[i]，直接用循环中的判断即可

二.2. 代码

#include<iostream>

#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rrep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rrep_gt(i, a, b) for(int i = (b); i > (a); -- i)

using namespace std;

const int N = 1e3 + 5;

int val[N], vol[N];
int res[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 0, container = 0;
    cin >> n >> container;
    _rep_le(i, 1, n) {
        cin >> vol[i] >> val[i];
    }

    // res[0] = 0;
    _rep_le(i, 1, n) {
        _rrep_ge(j, vol[i], container) {
            int temp = res[j - vol[i]] + val[i];
            res[j] = res[j] > (temp) ? res[j] : temp;
        }
    }

    cout << res[container] << endl;

    return 0;
}

二.3. 输入时就可以处理

可以发现处理数据时的外层循环和输入的循环一致。

• 求解时候的外层循环：得到前 i 个物品时可以得到的最大价值。因此是从前往后依次遍历第 i 个物品。
• 输入时，恰是从前往后得到第 i 个物品的体积和价值。

因此可以在输入时就处理数据，但是执行速度不一定比较快。因为处理输入需要用到 IO，程序执行 IO 操作依赖系统调用。在执行IO系统调用和处理数据之间来回切换破坏了程序的局部性，因此不一定快，但是代码量少。

二.4. 代码

#include<iostream>

#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rrep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rrep_gt(i, a, b) for(int i = (b); i > (a); -- i)

using namespace std;

const int N = 1e3 + 5;

int val[N], vol[N];
int res[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 0, container = 0;
    cin >> n >> container;
    _rep_le(i, 1, n) {
        cin >> vol[i] >> val[i];
        _rrep_ge(j, vol[i], container) {
            int temp = res[j - vol[i]] + val[i];
            res[j] = res[j] > (temp) ? res[j] : temp;
        }
    }

    cout << res[container] << endl;

    return 0;
}

三. 扩展

res 数组（即设计的状态数组）的初始化与状态转换有关系，从而影响了 res[container] 是否能够得到答案。

• 若状态数组(res或f)全部初始化为0。那么 res[container] 可以得到最大值，且其含义是 i 个物品，总容量为 container 时，能够取得的最大值。
  • 假设 res[k] 取得最大值其方案由一些列物品的选取，从 res[0] 转移而来。那么 res[container] 也可以从 res[container - k] （初始值为 0）以同样的方案转移到 res[container]。（有点像带了个 offset）
• 若状态数组中容量为 0 时，价值初始化为 0，其余全初始化为 $-INF$。那么同样的计算过程，我们可以得到这 i 个物品可以组合的各种体积之和及其对应的最大价值。
  • 若 $res[container] \neq -INF$ 那么可以得到体积之和恰为 m 的最大价值。
  • 否则，若求这 i 个物品所能得到的最大价值，应遍历最后得到的数组，取其最大值