代码随想录算法训练营Day35

第九章 动态规划part03

正式开始背包问题，背包问题还是挺难的，虽然大家可能看了很多背包问题模板代码，感觉挺简单，但基本理解的都不够深入。

如果是直接从来没听过背包问题，可以先看文字讲解慢慢了解 这是干什么的。

如果做过背包类问题，可以先看视频，很多内容，是自己平时没有考虑到位的。

背包问题，力扣上没有原题，大家先了解理论，今天就安排一道具体题目。

详细布置

01背包问题 二维

代码随想录

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, bagweight;// 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数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化, 因为需要用到dp[i - 1]的值
    // j < weight[0]已在上方被初始化为0
    // j >= weight[0]的值就初始化为value[0]
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    for(int i = 1; i < weight.size(); i++) { // 遍历科研物品
        for(int j = 0; j <= bagweight; j++) { // 遍历行李箱容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][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;

    return 0;
}

01背包问题 一维

代码随想录

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

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int kind,space;
    cin>>kind>>space;
    vector<int> sp(kind,0);
    vector<int> value(kind,0);
    vector<int> dp(space+1,0);
    for(int i=0;i<kind;i++) cin>>sp[i];
    for(int i=0;i<kind;i++) cin>>value[i];
    
    for(int i=0;i<kind;i++){
        for(int j=space;j>=sp[i];j--){
            dp[j]=max(dp[j],dp[j-sp[i]]+value[i]);
        }
    }
    
    cout<<dp[space];
    
    return 0;
}

416. 分割等和子集

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

代码随想录

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

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%2!=0) 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>=0;j--){
                if(j>=nums[i])
                    dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target]==target;
    }
};