关于01背包问题(入门)

huangliwei · 2024-08-10 23:27:46 · 个人记录

01背包问题

目录

1——问题概览

2——DP实现(状态转移方程推论)

3——对于01背包问题的优化 二维到一维

问题概览

难度：普及 题目：YBT1267 01背包问题(模版)

描述：

一个旅行者有一个最多能装M公斤的背包，现在有n件物品

它们的重量分别是W_1，W_2，...,W_n,它们的价值分别为C_1,C_2,...,C_n

求旅行者能获得最大总价值。

DP实现(状态转移方程推论)

首先为什么要叫这为01背包问题？？？

由题可得，对于任一物品只有拿取或者不拿这两种选择(对于一次选择，执行或不执行)

因此也就由"01"代表这个意思了，这是背包问题的root也是最简单的背包问题

如果用普通的搜索来解决，时间复杂度是O(2^n)，这简直惊为天人！！！

思考下，我们可以把问题分阶段为取第i件物品且容量为v时可获得的最大价值，从第1件商品与背包容量为1时开始往后递推，找到每一阶段的最大值，最终肯定能找到全局最优解，满足动态规划的最优子结构特点

因为前面i-1物品已经为最优了，所以只需要看放第i个物品和不放第i个物品所获的价值哪个大

但放下也有前提条件，就是第i个物品重量要小于当前背包容量v，不然你就算把背包掏空也塞不下......

简易分析得以下结论

A.放不了：直接不放这个物品，最优解——放这个物品前的最优解

B.放得下：

a.先清空背包，只放这个物品，再看看剩余容量能否装下之前的物品，最优解——这个物品的价值+背包剩余容量的最优解

b.不放这个物品，最优解——放这个物品前的最优解

然后，a、b 情况进行比较，选出真正的最优解

设DP[i][v]为当操作物品为i个,背包容量为v时所获最大价值

状态转移方程就是DP[i][v]=max(DP[i-1][v],DP[i-1][v-i.weight]+i.value)

注：i.weight指第i件物品的重量 value指第i件物品的价值

代码实现如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct WC{ll weight,value;};//weight重量 value价值 
ll n,m;//n件物品,m背包容量
WC a[205];//存储物品结构体数组
ll DP[205][205];//当操作物品数为i,背包容量为v时所获最大价值 
ll maxn(ll x,ll y){
    if(x>y){return x;}
    else{return y;}
} 
int main(){
    memset(DP,0,sizeof DP);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].weight>>a[i].value;
    }//输入
    for(int i=1;i<=n;i++){//递推每一个物品操作,对于任一物品只有拿或不拿两行为 
        for(int v=1;v<=m;v++){//递推容量的每一种情况 
            if(a[i].weight>v){//对于当前物品,超过容量上限,放不下的情况 
                DP[i][v]=DP[i-1][v];//等于上一个物品操作时所获最大价值,相当于没放 
            } 
            else{//如果可以放下 
                DP[i][v]=maxn( DP[i-1][v] , DP[i-1][v-a[i].weight]+a[i].value );
                //考虑不放和放哪一个的价值更大,哪个大存哪个 
            }
        } 
    } 
    cout<<DP[n][m];//当n个物品都完成操作,且m的容量都被分配时即为最大
    //直接输出DP[n][m]
    return 0;
}

对于01背包问题的优化 二维到一维

其实对于01背包的时间已经到O(M*N)了，没法再优化了 但对于空间却可以进一步压缩

我们重新定义DP[v]为背包容量为v下所获的最大价值

根据我们上文的分析DP[i][v]=max(DP[i-1][v],DP[i-1][v-i.weight]+i.value)

其中DP[i-1][v]和DP[i-1][v-i.weight]都是上一次操作时，容量为v和v-i.weight下所得最大价值

可知每一次的DP[i][v]都依赖上一轮的最大值

但是我们可以使用逆推来省去[i-1]的步骤，因为在一轮i之后的i+1轮中DP[v]存储的都是上一次所能获得的最大值

这就使得DP[v-i.weight]代替了DP[i-1][v-i.weight]的功能，并且压缩了空间

状态转移方程为：DP[v]=max(DP[v],DP[v-i.weight]+i.value)

注：DP[v]为不放时所获的值 DP[v-i.weight]+i.value为放时所获的值

这样在优化后01背包的空间复杂度为O(M)了 优化代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct WC{ll weight,value;};//weight重量 value价值 
ll n,m;//n件物品,m背包容量
WC a[205];//存储物品结构体数组
ll DP[205];//当背包容量为v下所能获最大价值 
ll maxn(ll x,ll y){
    if(x>y){return x;}
    else{return y;}
} 
int main(){
    memset(DP,0,sizeof DP);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].weight>>a[i].value;
    }//输入
    for(int i=1;i<=n;i++){
        for(int v=m;v>=a[i].weight;v--){//逆推 
            DP[v]=maxn(DP[v-a[i].weight]+a[i].value,DP[v]);
        }
    }
    cout<<DP[m];
    return 0;
}