CSP WIKI

简介与概述、功能介绍

在信息学竞赛（OI）里，01背包问题是动态规划算法中的经典问题。“01”意味着对于每个物品，我们只有两种选择：要么把它放进背包，要么不放进背包，不能只放一部分。该问题的核心功能是在给定背包容量和一系列物品的重量与价值后，找出能让背包内物品总价值最大的选择方案。

适用场景

01背包问题在实际生活中有广泛的应用。比如，你有一个容量固定的行李箱，还有一堆不同重量和重要性的物品，你要在行李箱容量限制下，选择尽可能重要的物品放入；再如，你有一定的资金和多种不同价格与收益的投资项目，在资金有限的情况下，挑选能带来最大收益的项目组合，这些都可以抽象为01背包问题来解决。

算法原理详解

状态定义

设 f[i][j] 表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值。

状态转移方程

考虑转移。假设当前已经处理好了前 $i-1$ 个物品的所有状态，那么对于第 $i$ 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 $f_{i-1,j}$ ；当其放入背包时，背包的剩余容量会减小 $w_{i}$ ，背包中物品的总价值会增大 $v_{i}$ ，故这种情况的最大价值为 $f_{i-1,j-w_{i}}+v_{i}$ 。

由此可以得出状态转移方程：

f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i})

初始化

当 i = 0 或者 j = 0 时，f[i][j] = 0，因为没有物品或者背包容量为 0 时，最大价值肯定是 0。

经典例题及代码实现

题面

有一个容量为 V 的背包和 n 个物品，每个物品有对应的重量 w[i] 和价值 v[i]。要求在不超过背包容量的前提下，选择一些物品放入背包，使得背包内物品的总价值最大。

输入输出样例

输入：第一行包含两个整数 n 和 V，分别表示物品的数量和背包的容量。接下来的 n 行，每行包含两个整数 w[i] 和 v[i]，表示第 i 个物品的重量和价值。

示例输入：

输出：输出一个整数，表示背包能装下的物品的最大总价值。

示例输出：

代码实现

示例代码

#include <iostream>
using namespace std;
 
const int N = 1010;
int n, V;
int w[N], v[N];
int f[N][N];
 
int main() {
    // 读入物品数量和背包容量
    cin >> n >> V;
    // 读入每个物品的重量和价值
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
 
    // 动态规划过程
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= V; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= w[i]) {
                f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
            }
        }
    }
 
    // 输出结果
    cout << f[n][V] << endl;
    return 0;
}

f_j=\max \left(f_j,f_{j-w_i}+v_i\right)

需要注意的是，在使用一维数组时，内层循环需要从大到小遍历，因为如果从小到大遍历，会导致 f[j - w[i]] 被提前更新，从而影响后续计算。

代码实现

示例代码

#include <iostream>
using namespace std;
 
const int N = 1010;
int n, V;
int w[N], v[N];
int f[N];
 
int main() {
    // 读入物品数量和背包容量
    cin >> n >> V;
    // 读入每个物品的重量和价值
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
 
    // 动态规划过程，滚动数组优化
    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= w[i]; j--) {
            f[j] = max(f[j], f[j - w[i]] + v[i]);
        }
    }
 
    // 输出结果
    cout << f[V] << endl;
    return 0;
}

例题

Status

Problem

背包DP

简介与概述、功能介绍

适用场景

算法原理详解

状态定义

状态转移方程

初始化

经典例题及代码实现

题面

输入输出样例

代码实现

滚动数组优化空间教程

优化原理

状态转移方程变化

代码实现

例题

On this page