【背包九讲】01背包问题

本文主要是介绍【背包九讲】01背包问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、01背包问题描述

已知：有 N 件物品和一个容量为 V 的背包。第i件物品的重量为w[i]，得到的价值是 c[i].
问题：求解将哪些物品装入背包可使价值总和最大。
条件：每种物品只有一件，可以选择放或者不放

2、基本思路

01背包的特点：每种物品只有一件，可以选择放或者不放

子问题定义状态

F[i][v] :前i件物品放到一个容量为V的背包中的最大价值

状态转移方程

F[i][v] = max(F[i-1][v],F[i-1][v-w[i]]+c[i])

分析：
考虑到子问题的状态定义，将前i件物品都放到容量为V的背包中，那么第i件物品有两种选择：放&不放；
（1）当选择第i将物品不放入背包时，那么此时只有前i-1件物品放到容量为V的背包中，所以最大的价值为：F[i-1][v];
（2）当选择第i间物品放到背包时，那么此时前i-1件物品就会放到容量为V-w[i]的背包中，所以最大的价值为：F[i-1][v-w[i]+c[i]

举个栗子：
背包承重量10，5件物品，重量[2,3,3,4,6], 价值[1,2,5,9,4].

填表

每一行表示每件物品的重量（价值），每一列表示最大承重，填表的内容表示当前的最大价值。
填表的方法
例如最大承重为5，第二行就只需要考虑2(1)和3(2)的情况，
（1）如果不拿3(2),就只能选择上一行的物品，即只有2(1)这一种选择，价值为1；
（2）如果拿3(2)，物品的重量为3（价值为2），与此同时，还可以继续选择上一行的物品2(1)，最终选择的物品价值为3；
综上，选取物品的最大价值为3
总结
第i行，第j列的价值应该等于： max (dp[i-1][j], v[i]+ dp[i-1][j-w[i]])

代码实现

//01背包
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int maxValue(int n, int c, vector<int> v, vector<int> w) 
{int **dp = new int*[n];//初始化for (int i = 0; i < n; i++) {dp[i] = new int[c + 1];for (int j = 0; j <= c; j++){dp[i][j] = 0;}}//处理第一行for (int j = 0; j <= c; j++){dp[0][j] += (j >= w[0]) ? v[0] : 0;}for (int i = 1; i < n; i++) {for (int j = 0; j <= c; j++) {if (j < w[i]){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j]);}}}return dp[n - 1][c];
}int main() 
{int n = 0, capacity = 0;//物品数量、背包容量cin >> n >> capacity;vector<int> values(n, 0);//物品价值vector<int> weights(n, 0);//物品重量for (int j = 0; j < n; j++)cin >> weights[j];for (int i = 0; i < n; i++)cin >> values[i];cout << maxValue(n, capacity, values, weights) << endl;system("pause");return 0;
}

性能分析
时间复杂度为：O(nv)
空间复杂度为：O(nv)，其中n表示物品的数量，v表示背包的容量
时间复杂度不能在优化，但是空间复杂度可以继续优化为O(v)

3、空间复杂度优化

上述方法采用的是二维数组，可以继续优化为一维数组

状态定义：F[v] :前i件物品放到一个容量为V的背包中的最大价值
状态转移方程：F[v]=max(F[v],F[v-w[i]]+c[i])

代码实现

//01背包
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int maxValue_1(int n, int c, vector<int> v, vector<int> w)
{int *dp = new int[n];memset(dp, 0, sizeof(dp));for (int i = 1; i < n; i++){for (int j = c; j >= w[i]; j--){dp[j] = max(v[i] + dp[j - w[i]], dp[j]);}}return dp[c];
}int main()
{int n = 0, capacity = 0;//物品数量、背包容量cin >> n >> capacity;vector<int> values(n, 0);//物品价值vector<int> weights(n, 0);//物品重量for (int j = 0; j < n; j++)cin >> weights[j];for (int i = 0; i < n; i++)cin >> values[i];cout << maxValue_1(n, capacity, values, weights) << endl;system("pause");return 0;
}

4、初始化细节问题

在求解背包问题时，事实上有两种不太相同的问法。
有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。
这两种问法的实现方法是在初始化的时候有所不同。

（1）第一种问法，要求恰好装满背包，那么在初始化时除了 F[0] 为 0，其它F[1][v] 均设为 -∞ ，这样就可以保证最终得到的 F[V ] 是一种恰好装满背包的最优解。

（2）如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 F[n][v]全部设为 0。

原因：初始化的 F 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0了。