代码随想录算法训练营第三十天 | 01背包问题 二维 01背包问题 一维 416. 分割等和子集

46. 携带研究材料（第六期模拟笔试）

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。 

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入描述

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。 

第三行包含 M 个正整数，代表每种研究材料的价值。

输出描述

输出一个整数，代表小明能够携带的研究材料的最大价值。

输入示例

6 1
2 2 3 1 5 2
2 3 1 5 4 3

输出示例

5

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

int n,bagweight;

void solvation()
{
    std::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(weight.size(),vector<int>(bagweight+1,0));
    
    for(int i = weight[0] ; i <= bagweight ; i ++)
    {
        dp[0][i] = value[0];
    }
    
    for(int i = 1; i < weight.size() ; i++)
    {
        for(int j = 0; j <= bagweight ; j ++)
        {
            if(weight[i] > j) 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[weight.size() - 1][bagweight];
}


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

滚动数组的写法：

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

int n ,bagweight;

void solveproblem()
{
    std::vector<int> weight(n);
    vector<int> value(n);
    
    for(int i = 0; i < n; i++)
    {
        cin >> weight[i];
    }
    for(int i = 0; i < n; i++)
    {
        cin >> value[i];
    }
    
    vector<int> dp(bagweight+1,0);
    
    for(int i = 0 ; i < weight.size(); i++)
    {
        for( int j = bagweight ; j >= weight[i] ; j--)
        {
            if(j < weight[i]) dp[j] = dp[j-1];
            else dp[j] = max(dp[j],dp[j - weight[i]] + value[i]);
        }//注意这里不是max(dp[j-1])
    }
    
    cout << dp[bagweight] <<endl;
}

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

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集

class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        int sum = 0;
        vector<int> dp(20000,0);
        for(int i = 0 ; i < nums.size() ; i++)
        {
            sum += nums[i];
        }
        if(sum%2 == 1) return false;

        int mid = sum/2;

        for(int i = 0 ; i < nums.size(); i++)
        {
            for(int j = mid ; j >= nums[i] ; j--)
            {
                dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]);
            }
        }
        if(dp[mid] == mid) return true;
        return false;
    }
};