/*
一维DP解法
*/
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N], w[N];
int n, m;

int main(){
    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 = m;j >= v[i];j --)
        {

            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    cout << f[m] << endl;
}

二维 DP 与一维 DP 的对比

二维 DP 解法

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

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

int main()
{
    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 = 0;j <= m;j ++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
}

在这个解法中，f[i][j] 表示前 i 件物品，在背包容量为 j 时的最大价值。状态转移方程为：

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

这里，我们需要保存每一件物品对应的状态，因此使用了二维数组。

一维 DP 解法

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

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

int main()
{
    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 = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

在这个解法中，f[j] 表示在背包容量为 j 时的最大价值。通过优化，我们只使用了一维数组来存储状态。

为什么可以将二维 DP 转化为一维 DP

状态转移的依赖性

在二维 DP 中，状态 f[i][j] 只依赖于前一层的状态 f[i-1][j] 和 f[i-1][j - v[i]]。这意味着当前层的计算只需要上一层的数据，而不需要更早的层。因此，可以利用这一点，通过滚动数组（Rolling Array）的方法，只保留上一层的数据，从而减少空间复杂度。

一维 DP 的实现原理

将二维 DP 转化为一维 DP 的关键在于逆序遍历背包容量。具体原因如下：

1. 避免重复使用同一物品：在 0-1 背包问题中，每件物品只能使用一次。如果采用从小到大的顺序遍历背包容量 j，可能会导致同一物品被多次使用（因为 f[j - v[i]] 可能已经包含了当前物品）。通过逆序遍历，可以确保每件物品在计算过程中只被使用一次。

2. 状态更新的正确性：逆序遍历确保在计算 f[j] 时，f[j - v[i]] 仍然是上一层（即未考虑当前物品之前）的状态，从而保持状态转移方程的正确性。

详细解释

二维 DP 的状态转移

在二维 DP 中，状态转移方程为：

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

这意味着当前物品 i 是否被选择，取决于是否选择当前物品 i 后的价值是否更大。为了实现这一点，我们需要保存前一层所有背包容量下的最大价值。

一维 DP 的状态转移

在一维 DP 中，我们使用数组 f[j] 来表示当前背包容量 j 下的最大价值。状态转移方程类似，但需要通过逆序遍历来确保每个物品只被使用一次：

f[j] = max(f[j], f[j - v[i]] + w[i])

通过逆序遍历 j，可以确保 f[j - v[i]] 是在当前物品 i 之前的状态，而不是包含了当前物品 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]);

这里，外层循环遍历每一件物品，内层循环从 m 逆序遍历到 v[i]。这样做的好处是：

• 保持状态的独立性：当前物品 i 的计算不会影响到同一轮内后续的容量 j，因为已经处理过的 j 的值不会被当前物品重复使用。

• 节省空间：只需要一个一维数组 f[j]，而不需要二维数组 f[i][j]，大大减少了空间复杂度。

空间复杂度的优化

二维 DP 的空间复杂度为 O(n * m)，其中 n 是物品数量，m 是背包容量。而一维 DP 的空间复杂度为O(m)，显著降低了空间需求，尤其在 n 和 m 较大时效果更加明显。