【背包问题】01背包

用户11719958

发布于 2025-12-30 14:46:52

5760

一，01背包问题详解

01背包问题是一种动态规划问题，动态规划问题的核心就是状态转移方程，本文主要讲述01背包问题。

本题链接：【模板】01背包_牛客题霸_牛客网

问题描述：

01背包问题可以描述如下：

有一个容量为V的背包，还有n个物品。现在忽略物品的实际几何形状，我们认为只要背包的剩余容量大于物体体积，就可以装入该物品。且每个物品只能选一次或者不选。每个物品都有两个属性：体积v和价值w

问：向背包中装入物品，不必装满和装满两种情况下的最大总价值时多少？

问题分析：

首先，我们容易想到的是将状态表示定义为：dp[i]表示，以第i个商品为结尾，所能装的最大价值。而这样定义，就会面临一个问题，我们在装第i个物品时，不知道背包的剩余容量是否满足物品的体积。所以这个状态表示是不行的，我们可以再加上一个条件：

dp[i][j]：以第i个物品为结尾，商品总体积不超过j，此时所能装的最大价值。

上述我们解决的时第一问，同样第二问也是如此，只是状态表示发生一点变化即可。

dp[i][j]：以第i个物品为结尾，商品总体积正好等于j，此时所能装的最大价值。

与第一问不同的是，我们想要正好凑成体积等于j的情况可能不存在，我们把这种状态的结果用-1来表示作区分。

代码：

#include <iostream>
#include <string.h>

using namespace std;

const int N=1010;
int v[N],w[N];
int dp[N][N];

int main()
{
    int n,V;
    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++)
    {
        dp[i][j]=dp[i-1][j];
        if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
    }
    cout<<dp[n][V]<<endl;

    //第二问
    memset(dp,0,sizeof dp);
    for(int j=1;j<=V;j++)
    dp[0][j]=-1;

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

    return 0;
}

空间优化：

优化后代码：

#include <iostream>
#include <string.h>

using namespace std;

const int N=1010;
int v[N],w[N];
int dp[N];

int main()
{
    int n,V;
    cin>>n>>V;

    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];
    //从右向左遍历dp，从左向右会被覆盖
    for(int i=1;i<=n;i++)
    for(int j=V;j>=v[i];j--)
    {
     dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
    cout<<dp[V]<<endl;

    memset(dp,0,sizeof dp);
    for(int j=1;j<=V;j++)
    dp[j]=-1;

    for(int i=1;i<=n;i++)
    for(int j=V;j>=v[i];j--)
    {
        if(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;
}

二，典例

1，分割等和子集

题目链接：LCR 101. 分割等和子集 - 力扣（LeetCode）

题目解析：

判断一个数组是否可以分成元素和相等的两部分。

算法解析：

本题的关键在于，是否可以做到问题的转化。对于一个数组我们可以知道它的所有元素的和sum,那么我们就可以得到这两部分元素的和都为sum/2。而我们只要知道一个数组是否可以凑成sum/2，如果可以，那么该数组就可以分成元素相等的两部分，返回true。否则返回false。

这样我们就把问题转化成了一个数组是否可以凑成sum/2，数组相当于物品，背包容量为sum/2，从数组中选取元素，装入背包。

代码：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(int x:nums) sum+=x;
        if(sum%2)
        return false;

        vector<vector<bool>> dp(n+1,vector<bool>(sum/2+1));
        for(int i=0;i<=n;i++)
        dp[i][0]=true;

        for(int i=1;i<=n;i++)
        for(int j=1;j<=sum/2;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=nums[i-1])
            dp[i][j]=dp[i][j]||dp[i-1][j-nums[i-1]];
        }
        return dp[n][sum/2];


    }
};

空间优化：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(int x:nums) sum+=x;
        if(sum%2) return false;

        int aim=sum/2;
        vector<bool> dp(aim+1);
        dp[0]=true;
        for(int i=1;i<=n;i++)
        for(int j=aim;j>=nums[i-1];j--)
        dp[j]=dp[j]||dp[j-nums[i-1]];

        return dp[aim];
    }
};

2，目标和

题目链接：LCR 102. 目标和 - 力扣（LeetCode）

题目解析：

向一个整数数组nums的元素前加'+'或者'-'，产生的表达式，使其运算后的值等于目标和target，求不同表达式的数目。

算法解析：

与上题一样，本题的关键在于第一步的问题转化。同样，对于一个数组，我们可以求出所有元素的和sum。题目描述，我们可以在元素前添上+/-，那么这个数组就可以被分成两部分，一部分是所有元素都是正的，另一部分的元素都是负的，假设所有元素都是正数的这部分和为a，而所有元素都是负数的和为b（b是这部分元素和的绝对值，b是大于0的）。

那么就可以得到a+b=sum，同时如果满足题目要求，可以得到a-b=target。联立可以得到

a=(target+sum)/2，target和sum都是已知的。此时，问题就转化成了，是否可以在数组中找到和正好等于a的不同选法。

代码：

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

空间优化：

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-25，如有侵权请联系 [email protected] 删除

优化

int

sum

数组

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 [email protected] 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度