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

发布时间:2024年01月03日

【模板】01背包_牛客题霸_牛客网你有一个背包,最多能容纳的体积是V。 现在有n个物品,第i个物品的体积为 ,。题目来自【牛客题霸】icon-default.png?t=N7T8https://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。

解题思路:

算法思路:
背包问题的状态表??常经典,如果?家不知道怎么来的,就把它当成?个「模板」记住吧~
我们先解决第?问:
1. 状态表?:
dp[i][j] 表?:从前 i 个物品中挑选,总体积「不超过」 j ,所有的选法中,能挑选出来
的最?价值。
2. 状态转移?程:
线性 dp 状态转移?程分析?式,?般都是根据「最后?步」的状况,来分情况讨论:
i. 不选第 i 个物品:相当于就是去前 i - 1 个物品中挑选,并且总体积不超过 j 。此
dp[i][j] = dp[i - 1][j]
ii. 选择第 i 个物品:那么我就只能去前 i - 1 个物品中,挑选总体积不超过 j - v[i]
的物品。此时 dp[i][j] = dp[i - 1][j - v[i]] + w[i] 。但是这种状态不?
定存在,因此需要特判?下。
综上,状态转移?程为: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] +
w[i])
3. 初始化:
我们多加??,?便我们的初始化,此时仅需将第??初始化为 0 即可。因为什么也不选,也能
满?体积不?于 j 的情况,此时的价值为 0
4. 填表顺序:
根据「状态转移?程」,我们仅需「从上往下」填表即可。
5. 返回值:
根据「状态表?」,返回 dp[n][V]
接下来解决第?问:
第?问仅需微调?下 dp 过程的五步即可。
因为有可能凑不? j 体积的物品,因此我们把不合法的状态设置为 -1
1. 状态表?:
dp[i][j] 表?:从前 i 个物品中挑选,总体积「正好」等于 j ,所有的选法中,能挑选出
来的最?价值。
2. 状态转移?程:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])
但是在使? dp[i - 1][j - v[i]] 的时候,不仅要判断 j >= v[i] ,?要判断 dp[i
- 1][j - v[i]] 表?的情况是否存在,也就是 dp[i - 1][j - v[i]] != -1
3. 初始化:
我们多加??,?便我们的初始化:
i. 第?个格?为 0 ,因为正好能凑?体积为 0 的背包;
ii. 但是第??后?的格?都是 -1 ,因为没有物品,?法满?体积?于 0 的情况。
4. 填表顺序:
根据「状态转移?程」,我们仅需「从上往下」填表即可。
5. 返回值:
由于最后可能凑不成体积为 V 的情况,因此返回之前需要「特判」?下。
(别急着?开,后?还有优化)

解题代码:

#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?。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

解题思路:

算法思路:
先将问题转化成我们「熟悉」的题型。
如果数组能够被分成两个相同元素之和相同的?集,那么原数组必须有下??个性质:
i. 所有元素之和应该是?个偶数;
ii. 数组中最?的元素应该?于所有元素总和的?半;
iii. 挑选?些数,这些数的总和应该等于数组总和的?半。
根据前两个性质,我们可以提前判断数组能够被划分。根据最后?个性质,我们发现问题就转化成
了「01 背包」的模型:
i. 数组中的元素只能选择?次;
ii. 每个元素?临被选择或者不被选择的处境;
iii. 选出来的元素总和要等于所有元素总和的?半。
其中,数组内的元素就是物品,总和就是背包。
那么我们就可以?背包模型的分析?式,来处理这道题。
请?家注意,「不要背」状态转移?程,因为题型变化之后,状态转移?程就会跟着变化。我们要
记住的是分析问题的模式。?这种分析问题的模式来解决问题。
1. 状态表?:
dp[i][j] 表?在前 i 个元素中选择,所有的选法中,能否凑成总和为 j 这个数。
2. 状态转移?程:
?规矩,根据「最后?个位置」的元素,结合题?的要求,分情况讨论:
i. 不选择 nums[i] :那么我们是否能够凑成总和为 j ,就要看在前 i - 1 个元素中
选,能否凑成总和为 j 。根据状态表?,此时 dp[i][j] = dp[i - 1][j]
ii. 选择 nums[i] :这种情况下是有前提条件的,此时的 nums[i] 应该是?于等于 j
因为如果这个元素都?要凑成的总和?,选择它就没有意义呀。那么我们是否能够凑成总和
j ,就要看在前 i - 1 个元素中选,能否凑成总和为 j - nums[i] 。根据状态表
?,此时 dp[i][j] = dp[i - 1][j - nums[i]]
综上所述,两种情况下只要有?种能够凑成总和为 j ,那么这个状态就是 true 。因此,状态转
移?程为:
dp[i][j] = dp[i - 1][j]
if(nums[i - 1] <= j) dp[i][j] = dp[i][j] || dp[i - 1][j -
nums[i]]
3. 初始化:
由于需要?到上??的数据,因此我们可以先把第??初始化。
第??表?不选择任何元素,要凑成?标和 j 。只有当?标和为 0 的时候才能做到,因此第?
?仅需初始化第?个元素 dp[0][0] = true
4. 填表顺序:
根据「状态转移?程」,我们需要「从上往下」填写每??,每??的顺序是「?所谓的」。
5. 返回值:
根据「状态表?」,返回 dp[n][aim] 的值。
其中 n 表?数组的??, aim 表?要凑的?标和。
6. 空间优化:
所有的「背包问题」,都可以进?空间上的优化。
对于 01背包类型的,我们的优化策略是:
i. 删掉第?维;
ii. 修改第?层循环的遍历顺序即可。

?解题代码:

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];
    }
};

文章来源:https://blog.csdn.net/m0_69061857/article/details/135027767
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。