动态规划~01背包问题

01背包问题
经典的0 - 1背包问题的解决方案。

二维数组的版本

代码功能概述

0 - 1背包问题指的是有 n 个物品和一个容量为 m 的背包，每个物品有对应的体积 v[i] 和价值 w[i]，需要从这些物品里挑选若干个放入背包，让背包内物品的总价值达到最大。每个物品仅能选择放入或者不放入背包（即0 - 1选择）。

代码详细解释

#include<bits/stdc++.h>
using namespace std;

// 定义长整型别名
typedef long long LL;
// 定义数组的最大长度
const int N=1100;

// f[i][j] 表示前 i 个物品，背包容量为 j 时的最大价值
int f[N][N];
// v[i] 表示第 i 个物品的体积，w[i] 表示第 i 个物品的价值
int v[N],w[N];

int main(){
    // n 表示物品的数量，m 表示背包的容量
    int n,m;
    // 从标准输入读取物品数量和背包容量
    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 = 1;j <= m;j++){
            // 如果当前背包容量 j 小于第 i 个物品的体积 v[i]，则不能放入第 i 个物品
            if(j < v[i])
                // 最大价值等于前 i - 1 个物品在容量 j 下的最大价值
                f[i][j] = f[i-1][j];
            else
                // 可以选择放入或不放入第 i 个物品，取两者中的最大值
                f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    // 输出前 n 个物品，背包容量为 m 时的最大价值
    cout<<f[n][m];
    return 0;
}

代码核心逻辑

• 状态定义：f[i][j] 代表前 i 个物品，背包容量为 j 时所能获得的最大价值。
• 状态转移：
  • 若 j < v[i]，也就是当前背包容量不足以放入第 i 个物品，那么 f[i][j] = f[i - 1][j]。
  • 若 j >= v[i]，则可以选择放入或者不放入第 i 个物品：
    • 不放入：f[i][j] = f[i - 1][j]。
    • 放入：f[i][j] = f[i - 1][j - v[i]] + w[i]。
  • 取这两种情况的最大值作为 f[i][j] 的值。
• 最终结果：f[n][m] 即为前 n 个物品，背包容量为 m 时的最大价值。

复杂度分析

• 时间复杂度：$O(nm)$，这里的 n 是物品的数量，m 是背包的容量。
• 空间复杂度：$O(nm)$，主要是用于存储状态数组 f。

要将你的二维动态规划代码优化为一维数组，可以利用动态规划的状态转移只依赖于上一行的状态这一特性。通过从右到左更新一维数组，可以避免覆盖还未使用的状态，从而实现空间优化。

一维数组的版本

优化后的代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1100;

int f[N]; // 一维动态规划数组，f[j] 表示凑出金额 j 所需的最大价值
int v[N], w[N]; // v[i] 表示第 i 个物品的体积，w[i] 表示第 i 个物品的价值

int main() {
    int n, m;
    cin >> n >> m; // 输入物品数量 n 和背包容量 m
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i]; // 输入每个物品的体积和价值
    }

    // 初始化动态规划数组
    memset(f, 0, sizeof(f)); // 初始时，所有金额的最大价值为 0

    // 动态规划求解
    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; // 输出凑出金额 m 的最大价值
    return 0;
}

代码解释

1. 一维数组的定义

• 原代码使用二维数组 f[i][j] 表示前 i 个物品在背包容量为 j 时的最大价值。
• 优化后，使用一维数组 f[j] 表示背包容量为 j 时的最大价值。
• 因为状态转移只依赖于上一行的状态，所以可以用一维数组代替二维数组。

2. 从右到左更新

• 在更新 f[j] 时，f[j - v[i]] 表示未选择当前物品时的状态。
• 如果从左到右更新（如 for (int j = v[i]; j <= m; j++)），会导致 f[j - v[i]] 被当前物品更新过，从而出现重复选择当前物品的情况。
• 因此，必须从右到左更新（如 for (int j = m; j >= v[i]; j--)），确保每个物品只被选择一次。

3. 状态转移方程

• 状态转移方程保持不变：
  $$f[j]=\max (f[j],f[j-v[i]]+w[i])$$
  • f[j] 表示不选择当前物品时的最大价值。
  • f[j - v[i]] + w[i] 表示选择当前物品时的最大价值。

4. 初始化

• 初始化 f 数组为 0，表示在没有物品时，所有背包容量的最大价值都为 0。

5. 输出结果

• 最终结果存储在 f[m] 中，表示背包容量为 m 时的最大价值。

复杂度分析

时间复杂度

• 外层循环遍历物品数量 $n$，内层循环遍历背包容量 $m$。
• 时间复杂度为 $O(n\times m)$。

空间复杂度

• 使用了一维数组 f，空间复杂度为 $O(m)$。

注意事项

1. 从右到左更新的重要性：

   • 如果改为从左到右更新（如 for (int j = v[i]; j <= m; j++)），会导致每个物品被多次选择，变成 完全背包问题 的解法。
   • 因此，在 0-1 背包问题 中，必须从右到左更新。

2. 适用场景：

   • 这段代码适用于 0-1 背包问题，即每个物品只能选择一次。
   • 如果是 完全背包问题（每个物品可以无限次选择），需要将状态转移方程改为 f[j] = max(f[j], f[j - v[i]] + w[i])，并且内层循环改为从左到右更新。