01背包问题 二维

思路看了一遍，默写一下哈。甚至看了两遍，但是还没开始搞。。。振作起来！！！

目前看就是核心那一行有点问题，具体看备注吧，然后就是把验证代码也放上来了。

#include <iostream>
#include <vector>
using namespace ::std;
int main()
{
    int n;
    int bagweight;
    cin >> n;
    cin >> bagweight;
    // cout << "n是  " << n << endl;
    // cout << "bagweight  " << bagweight << endl;
    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];
    }
    // test
    // for (int i = 0; i < n; i++)
    // {
    //     cout << "weight是  " << weight[i] << endl;
    //     cout << "value是  " << value[i] << endl;
    // }
    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 = 0; j <= bagweight; j++)
        {
            if (weight[i] > j)
            {
                //这行实际上也做了第0列，第i行的赋值。
                dp[i][j] = dp[i - 1][j];
            }
            else
            {
                //要考虑 j - weight[i] 是前一个价值可能性
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 
            }
        }
    }
    // for (int i = 0; i < n; i++)
    // {
    //     for (int j = 0; j < bagweight; j++)
    //     {
    //         cout << " " << dp[i][j];
    //     }
    //     cout << endl;
    // }
    cout << dp[n-1][bagweight];
    return 0;
}

随想录的写法学习一下。

//二维dp数组实现
#include <bits/stdc++.h>
using namespace std;

int n, bagweight;// bagweight代表行李箱空间
void solve() {
    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++) { // 遍历行李箱容量
            // 如果装不下这个物品,那么就继承dp[i - 1][j]的值
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            // 如果能装下,就将值更新为 不装这个物品的最大值 和 装这个物品的最大值 中的 最大值
            // 装这个物品的最大值由容量为j - weight[i]的包任意放入序号为[0, i - 1]的最大值 + 该物品的价值构成
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
    cout << dp[weight.size() - 1][bagweight] << endl;
}

int main() {
    while(cin >> n >> bagweight) {
        solve();
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace ::std;
int main()
{
    int n;
    int bagweight;
    cin >> n;
    cin >> bagweight;
    // cout << "n是  " << n << endl;
    // cout << "bagweight  " << bagweight << endl;
    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];
    }
    // test
    // for (int i = 0; i < n; i++)
    // {
    //     cout << "weight是  " << weight[i] << endl;
    //     cout << "value是  " << value[i] << endl;
    // }
    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]); 
        }
    }

    //for (int j = 0; j < bagweight; j++)
    //{
    //    cout << " " << dp[i][j];
    //}
    //cout << endl;

    cout << dp[bagweight];
    return 0;
}

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