1.01背包问题 二维
代码：
#include <iostream>
#include <vector>
using namespace std;
int main(){int n,bagweight;cin >> n >> bagweight;vector<int> weight(n,0);vector<int> value(n,0);for(int i = 0; i < n; i++){cin >> weight[i];}for(int j = 0; j < n; j++){cin >> value[j];}// dp[i][j] 表示在容量为j的情况下，从【0，i】的物品里任取所能达到的最大价值vector<vector<int>> dp(n,vector<int>(bagweight + 1,0));for(int j = weight[0]; j <= bagweight; j++){dp[0][j] = value[0];}for(int i = 1; i < n; i++){for(int j = 1; j <= bagweight; j++){if(j < weight[i]){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i]);}}}cout << dp[n - 1][bagweight] << endl;
}note：
dp数组的含义：在容量为j的背包中，装入种类为[0,i]的物品，所能拥有的最大价值为value[i][j]
递推公式：如果容量不够weight[i]，dp[i][j] = dp[i - 1][j]；如果容量够，dp[i][j] = max(dp[i - 1][j] ,dp[i - 1][j - weight[i] + value[i])
dp数组的初始化：按照定义去进行初始化，因为所有的元素都依赖于上一行的元素，因此，只需要初始化第一行。第一行的元素，物品种类都是0，容量在变化——因此，将容量大于等于第0种物品的元素全部初始化为value[0]
遍历顺序：在二维数组里，先背包还是先物品，都没差。遍历顺序也是，不影响。
2.01背包问题 一维
代码随想录
视频讲解：带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！_哔哩哔哩_bilibili
代码：
#include <iostream>
#include <vector>
using namespace std;
int main(){int n,bagweight;cin >> n >> bagweight;vector<int> weight(n,0);vector<int> value(n,0);for(int i = 0; i < n; i++){cin >> weight[i];}for(int j = 0; j < n; j++){cin >> value[j];}// dp[i][j] 表示在容量为j的情况下，从【0，i】的物品里任取所能达到的最大价值vector<int> dp(bagweight + 1,0);for(int i = 0; i < n; i++){for(int j = bagweight; j >=weight[i]; j--){ // 确保每个物品只添加一次dp[j] = max(dp[j],dp[j - weight[i]] + value[i]);}}cout << dp[bagweight] << endl;
}note：
一维数组是对二维数组的压缩，因为在二维dp数组种，下一行的元素只需要依靠上一行的元素得出。因此，我们可以只用一个一维数组来实现——每次更新的时候，利用目前数组已有的旧数据去推出新数据。
dp数组的含义：容量为j的背包，装种类为[0,i]的物品，所能拥有的最大价值为dp[j]
递推公式：在容量大于等于物品i的种类时，dp[j] = max(dp[j],dp[j - weight[i]] + value[i] )
dp数组的初始化：dp[0] = 0
遍历顺序：由于一维数组其实是二维数组的“行”，因此为了不破坏这种压缩关系，以及这种递推关系——必须先遍历物品再遍历背包容量。
且，01背包不需要去依靠前一个元素去叠加个数，因此在遍历背包容量时要使用倒序遍历，保证每个元素只使用一次。
3.分割等和子集
代码随想录
视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集_哔哩哔哩_bilibili
代码：
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(int num:nums){sum += num;}if(sum % 2) return false;int target = sum / 2;vector<int> dp(target + 1,0);for(int i = 0; i < nums.size(); i++){for(int j = target; j >= nums[i]; j--){dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]);}}if(dp[target] == target) return true;return false;}
};note：
本题相当于问容量为j的背包可否装满 即dp[target ] == target
dp数组的含义：用下标为[0,i]的nums元素来装容量为j的背包所能装的最大价值为dp[j]，这里的价值和重量都是nums[i]
递推公式：在容量j大于等于nums[i]的前提下，dp[j] = max(dp[j],dp[j - nums[i]] + nums[i])
dp数组的初始化：dp[0] = 0
遍历顺序:本题使用的是一维01背包问题的模板，因此，要先遍历物品再遍历背包容量，且在遍历背包容量的时候要倒序遍历。
