代码随想录第四十一天打卡

01背包问题 二维

代码随想录

视频讲解：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

#include <iostream>
#include <vector>
using namespace std;
int n,bag;
void solve(){vector<int>weight(n,0);vector<int>value(n,0);for (int i=0;i<n;i++)cin>>weight[i];for (int i=0;i<n;i++)cin>>value[i];vector<vector<int>>dp(n,vector<int>(bag+1,0));for (int i=weight[0];i<=bag;i++)dp[0][i]=value[0];for (int i=1;i<n;i++){//物品for (int j=0;j<=bag;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][bag];
}
int main(){cin>>n>>bag;solve();return 0;
}

01背包问题 一维

代码随想录

视频讲解：带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！_哔哩哔哩_bilibili

#include <iostream>
#include <vector>
using namespace std;
int n, bag;
void solve() {vector<int>weight(n, 0);vector<int>value(n, 0);for (int i = 0; i < n; i++)cin >> weight[i];for (int i = 0; i < n; i++)cin >> value[i];vector<int>dp(bag + 1, 0);for (int i = 0; i < n; i++) {for (int j =bag ; j >=weight[i] ;j--) {dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bag] << endl;
}
int main() {cin >> n >> bag;solve();}

416. 分割等和子集

本题是 01背包的应用类题目

代码随想录

视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集_哔哩哔哩_bilibili
 

class Solution {
public:bool canPartition(vector<int>& nums) {int sum=0;for (int num:nums)sum+=num;if (sum%2==1)return false;else sum/=2;vector<int>dp(sum+1,0);for (int i=0;i<nums.size();i++){//物品for (int j=sum;j>=nums[i];j--){//背包容量dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);}}if (dp.back()!=sum)return false;else return true;}
};