【算法挨揍日记】day41——【模板】01背包、416. 分割等和子集

【模板】01背包_牛客题霸_牛客网你有一个背包，最多能容纳的体积是V。 现在有n个物品，第i个物品的体积为 ,。题目来自【牛客题霸】https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196#:~:text=%E4%BD%A0%E6%9C%89%E4%B8%80%E4%B8%AA%E8%83%8C%E5%8C%85,%E6%A8%A1%E6%9D%BF%E3%80%9101%E8%83%8C%E5%8C%85【模板】01背包_牛客题霸_牛客网

题目描述：

描述

你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为��vi??,价值为��wi?。

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述：

第一行两个整数n和V，表示物品个数和背包体积。

接下来n行，每行两个数��vi?和��wi?，表示第i个物品的体积和价值。

1≤�,�,��,��≤10001≤n,V,vi?,wi?≤1000

输出描述：

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

解题思路：

解题代码：

#include<iostream>
#include<vector>
using namespace std;
int n,V;
const int N=1010;
vector<int>v(N);
vector<int>w(N);
vector<vector<int>>dp1(N,vector<int>(N,0));
vector<vector<int>>dp2(N,vector<int>(N,0));

int main()
{
    cin>>n>>V;
   
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=V;j++)
        {
            dp1[i][j]=dp1[i-1][j];
            if(j-v[i]>=0)   dp1[i][j]=max(dp1[i][j],dp1[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<dp1[n][V]<<endl;

    for(int i=1;i<=V;i++)dp2[0][i]=-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=V;j++)
        {
            dp2[i][j]=dp2[i-1][j];
            if(j-v[i]>=0&&dp2[i-1][j-v[i]]!=-1)  dp2[i][j]=max(dp2[i][j],w[i]+dp2[i-1][j-v[i]]);
        }
    }
    cout<<(dp2[n][V]==-1?0:dp2[n][V])<<endl;
    return 0;
}

优化后：

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
int n,V;
const int N=1010;
vector<int>v(N);
vector<int>w(N);
int dp[N];

int main()
{
    cin>>n>>V;
   
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=1;j--)
        {
            dp[j]=dp[j];            
            if(j-v[i]>=0)   dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    
    cout<<dp[V]<<endl;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=V;i++)dp[i]=-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=1;j--)
        {
            dp[j]=dp[j];            
            if(j-v[i]>=0&&dp[j-v[i]]!=-1)   dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<(dp[V]==-1?0:dp[V])<<endl;
    return 0;
}

416. 分割等和子集

416.?分割等和子集

题目描述:

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

解题思路：

?解题代码：

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