AcWing中01背包问题

在acwing 中的题，本次为01背包问题【具体视频可通过 .acwing /video/214网站观看（ps:是跟着视频中的老师一起写的，并不是原创~~~）】

01背包问题题目：

        有N件物品和一个容量是V的背包。每件物品只能使用一次。第i间物品的体积是vi，价值是wi，求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，输出最大价值。

输入格式：

        第一行两个整数，N，V，用空格隔开，分别标识物品数量和背包容积。接下来的N行，每行两个整数vi，wi，用空格隔开，分别标识第i间物品的体积和价值。

输出格式：

        输出一个整数，表示最大价值。

数据范围：

        0<N   V<=1000

        0<vi  wi<=1000

输入样式：

4 5

1 2

2 4

3 4

4 5

输出样式：

8

 

代码  /* 二维动态规划： f[i][j]表示只看前面i个物品，总体积是j的情况下，总价值最大是多少 result = max(f[n][0~v]) f[i][j]: 1.不选第i个物品，f[i][j] = f[i-1][j] 2.选第i个物品，f[i][j] = f[i-1][j-v[i]] f[i][j] = max{1.2.} 初始化：f[0][0] = 0 时间复杂度：O（n*m） */ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; // 定义常量N，表示物品的最大数量 int n, m; // n表示物品的数量，m表示背包的容量 int f[N][N]; // f[i][j]表示前i个物品在背包容量为j时的最大价值 int v[N], w[N]; // v[i]表示第i个物品的体积，w[i]表示第i个物品的价值 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]; // 不选择第i个物品时的最大价值 if (j >= v[i]) // 如果当前背包容量j大于等于第i个物品的体积 f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]); // 选择第i个物品或不选择，取最大值 } } int res = 0; // 遍历所有可能的背包容量，找到最大价值 for (int i = 0; i <= m; i++) res = max(res, f[n][i]); cout << res << endl; // 输出最大价值 return 0; }

代码运行状态： Finished   

输入

10 100 5 8 32 47 17 43 7 9 6 4 29 40 2 6 14 31 6 17 1 3

输出

184

标准答案

184

解题思路

状态定义：

f[i][j] 表示前 i 个物品在背包容量为 j 时的最大价值。

状态转移方程：

对于每个物品 i，我们有两种选择：

不选择第 i 个物品：此时的最大价值为 f[i-1][j]。

选择第 i 个物品：此时的最大价值为 f[i-1][j-v[i]] + w[i]（前提是 j >= v[i]）。

因此，状态转移方程为：

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

初始化：

f[0][j] = 0，表示没有物品时，背包的最大价值为0。

f[i][0] = 0，表示背包容量为0时，最大价值为0。

最终结果：

最终的结果是 f[n][m]，即前 n 个物品在背包容量为 m 时的最大价值。