01背包問題 二維

鏈接

1. 遍歷物品沒有大小順序要求
2. 重點是模擬，推導出遞推公式

#include <iostream>
#include <vector>int main(){int m, n;std::cin>>m>>n;std::vector<int> weight(m,0),value(m,0);for(int i{0}; i<m; i++){std::cin>>weight[i];}for(int i{0}; i<m; i++){std::cin>>value[i];}std::vector<std::vector<int>> dp(m, std::vector<int>(n+1, 0));for(int i{0}; i<=n; i++){dp[0][i] = i>=weight[0]?value[0]:0;}for(int i{1}; i<m; i++){for(int j{0}; j<=n; j++){if(weight[i]<=j){dp[i][j] = std::max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);}else{dp[i][j] = dp[i-1][j];}}}std::cout<<dp[m-1][n]<<std::endl;//return 0;
}

01背包問題 一維

鏈接

1. 01背包問題可以用一維數組處理，但是需要注意遍歷背包的順序，應該從大到小遍歷，因為遍歷判斷是否應該放入當前物品時，需要比較當前物品放入后剩余空間的最大價值，此時如果當前背包容量大于當前物品空間的兩倍，則正序遍歷時會將其放入兩次，例：dp[j] = max(dp[j], dp[j-weight[i]+value[i])，若當前背包容量為5，物品重量為2，物品價值特別大，則比較未放入當前物品時的價值與背包容量為3時的價值與當前物品價值的和，這里假如是從小到大遍歷，則在判斷容量為3時，因為當前物品價值特別大，已經放入，會與當前再次放入矛盾，導致錯誤，所以應該從大到小遍歷，確保比較時當前物品沒有被放入比較過

#include <iostream>
#include <vector>int main(){int m, n;std::cin>>m>>n;std::vector<int> weight(m,0),value(m,0);for(int i{0}; i<m; i++){std::cin>>weight[i];}for(int i{0}; i<m; i++){std::cin>>value[i];}//std::vector<int> dp(n+1,0);for(int i{0}; i<m; i++){for(int j{n}; j>=weight[i]; j--){dp[j] = std::max(dp[j], dp[j-weight[i]]+value[i]);}}std::cout<<dp[n]<<std::endl;return 0;
}

416. 分割等和子集

1. 本質上也是01背包問題，相當于每個數字是一個物品，價值和體積都等于數字本身，有一個總和一半大小的背包，要求背包放入物品的價值總和盡量最大，最大是sum/2，如果能達到sum/2，說明可以劃分為兩個相同大小的子集

class Solution {
public:bool canPartition(vector<int>& nums) {int sum{0};for(const auto& val:nums){sum += val;}if(sum%2!=0){return false;}//std::vector<int> dp(sum/2+1,0);for(int i{0}; i<nums.size(); i++){for(int j{sum/2}; j>=nums[i]; j--){dp[j] = std::max(dp[j], dp[j-nums[i]]+nums[i]);}}return dp[sum/2]==sum/2;}
};