代码随想录算法训练营第四十四天

km46. 携带研究材料

题目链接：km46. 携带研究材料

1. 确定dp数组以及下标的含义：i的含义是物品编号从0到i，j的含义是当前背包的最大容量，dp[i][j]背包内物品的总价值
2. 确定递推公式：背包最大容量固定为j，每个循环尝试在当前最大容量下，把物品往背包里试着放一下，面临2种情况：
   1. 最大容量不够放入当前选择的物品，背包内最大的价值就是原来的dp[i-1][j]，
   2. 最大容量能放下当前选择的物品，价值为dp[i-1][j-space[i]]+value[i]，将space[i]这么多空间价值的物品取出，在把当前物品的价值放进去的总价值，或者不进行这个交换的总价值哪个更大
3. dp数组如何初始化：背包容量为0，没法放物品，价值就都是0，dp[0][0]到dp[i][0]都是0；背包总空间能放下第一个物品，包内物品的价值就是第一个物品的价值，dp[0][space[0]]到dp[0][j]都是value[0]。
4. 确定遍历顺序：从小到大
5. 打印dp数组。

#include <iostream>
#include <vector>
using namespace std;
int main(){int M;int N;std::cin>>M>>N;std::vector<int> space(M);std::vector<int> value(M);for(int i=0;i<M;i++){std::cin>>space[i];}    for(int i=0;i<M;i++){std::cin>>value[i];}vector<vector<int>>dp(M,vector<int>(N+1,0));for(int i =space[0];i<=N;i++){dp[0][i]=value[0];//能装的情况下把物品1都装进去}for(int i =1;i<M;i++){for(int j=0;j<=N;j++){if(j<space[i])dp[i][j] = dp[i-1][j];//当前物品占用空间大于背包空间，装不了else dp[i][j]=max(dp[i-1][j],dp[i-1][j-space[i]]+value[i]);//能装，把i物品需要空间的总价值减掉，再加上当前物品的价值，看看价值和不换哪个大// std::cout<<dp[i][j]<<" ";}// std::cout<<std::endl;}std::cout<<dp[M-1][N];return 0;
}

---

416. 分割等和子集

题目链接：416. 分割等和子集

1. 确定dp数组以及下标的含义：dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]
2. 确定递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3. 初始化：dp[0]=0
4. 确定遍历顺序：从大到小
5. 打印dp数组。

class Solution {
public:bool canPartition(vector<int>& nums) {int sum =0;for(int &i :nums){sum+=i;}if(sum%2==1)return false;int target = sum/2;vector<int>dp(100*100+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;    }
};

---