01背包

dsy2022 · 2023-07-09 15:05:39 · 个人记录

01背包

引言

首先，01 背包问题就如同他的标题，就是给你一个背包的总体积，而这个背包是能装载的物品数量是有限的。又给出了每个物品的价值与重量，对于每个物品只能选择拿或者不拿，且每个物品有且仅有一个，物品不可分割。在这种情况下，要我们求出我们能求出的物品价值最大值。

在拿到这道题的时候，我相信大部分人都会对这些物品的平均价值^{[1]}进行排序，然后依次选最大的往背包里填，可惜，这里并不能这样写，我们可以轻易地举出一个反例。

我们假如有这样一个数据：

背包最大承受重量：10
物品1重量：7    物品1价值：20
物品2重量：4    物品2价值：10
物品3重量：5    物品3价值：11

这时，如果按照我们刚刚写出的贪心，物品一的平均价值约为 2.85，比其他物品都大，所以我们可以得到的物品价值最大为 20。对吗？不对，我们可以看出，我们如果选择物品 2 个和物品 3 放入背包，得到的总价值为 21，比贪心得到的值还大！

那我们的贪心哪里出问题了呢？这很简单，问题出在题面的物品不可分割上。不可分割，就意味着我们需要把整个物品都放进背包。里这时如果物品很大，背包将会剩余很多的空间。而这时如果我们选择平均价值较小，但重量也较小的多个物品放入背包，可能因为我们浪费的空间变小了，反而我们的总价值还变大了。

那我们是不是贪心的时候还要分析平均价值次小的物品呢？不，如果我们这样分析，我们就会发现还是不行。于是我们就会继续去分析平均价值次次小的物品，次次次小的物品.....这样我们就落到了一个陷阱里。这时，我们就需要[DP]来帮忙了。

讲解

注意

接下来，我将用 a_i 来表示第 i 个物品的重量，用 b_i 来表示第 i 个物品的价值， f(i,j) 表示如果有 i 个物品，背包的重量为 j 时题目的答案

以下例题： P1048 [NOIP2005 普及组] 采药

我们先看看这道题的状态转移方程

其中，f(i-1,j-a_i)+b_i 表示加上此物品，f(i-1,j) 表示不要此物品。i-1 是因为我们要在 i-1 的基础上加 b_i ，而 j-a_i 是因为我们现在拿了这个物品，那么除这个物品以外的物品所占用的重量只能占用 j-a_i 才行，要不然装不下了。其他不进行解释。

可能听起来有点模糊，我以上面的例子列一个表格就明白了

我们以 i=3,j=9 为例，在这里，f(3,9) 是这样算的：

看懂了吗？看不懂也没办法了

我们可以看出，如果我们的DP没有边界（也叫初始值），是没法计算的。因为其他答案的递推都要依赖以前的答案。这道题目中DP的边界就是当 i 等于 0 时答案为 0 ，因为如果我们没有物品来放进背包里。当 j 等于 0 时同理，因为我们的背包没法容纳物品。这样，我们就可以DP下去了。

其他见代码。

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

int a[1005],b[1005]; 
int ans[1005][1005]; //同f

int main(){ 
    int t,m; 
    cin>>t>>m; 
    for(int i=1;i<=m;i++){ 
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=m;i++){ 
        for(int j=1;j<=t;j--){ 
            if(j>=a[i]){  //为了防止下标出现小于0的情况
                ans[i][j]=max(ans[i-1][j-a[i]]+b[i],ans[i-1][j]); 
            }else{ 
                ans[i][j]=ans[i-1][j]; 
            } 
        } 
    } 
    cout<<ans[m][t]; 
    //system("pause"); 
    return 0; 
}

我们可以发现，ans 数组的 i 值没有也能用，不过 j 要从 t 开始枚举，否则后面递推所需要的数据会被覆盖，于是就又有了以下空间优化（滚动数组）的代码：

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

int a[1005],b[1005]; 
int ans[1005]; //这里优化掉了一维

int main(){ 
    int t,m; 
    cin>>t>>m; 
    for(int i=1;i<=m;i++){ 
        cin>>a[i]>>b[i]; 
    } 
    for(int i=1;i<=m;i++){ 
        for(int j=t;j>=1;j--){ //注意这里
            if(j>=a[i]){ 
                ans[j]=max(ans[j-a[i]]+b[i],ans[j]); 
            } //有没有发现少了一点东西？这是因为去掉了第一维后ans[i][j]=ans[i-1][j]相当于ans[j]=ans[j]，已经没有用了
        } 
    } 
    cout<<ans[t]; 
    //system("pause"); 
    return 0; 
}

完全背包

以下例题

P2722 [USACO3.1] 总分 Score Inflation

在上文 01 背包中，我们的物品有且仅有一个，而在完全背包中，我们的物品个数是无限的。看起来有点难度，但还记得我上文说的话吗？

的答案都是在背包可承载重量为 $j$ 时尽可能放入第 $i$ 个物品，导致第 $i$ 个物品被重复放置，变成一 个完全背包。

所以，我们把状态转移方程改一改，就成了这样

那有人会说了：你怎么知道如果把 i − 1 改成 i 就是完全背包了呢？很简单，我还是以上面的例子列个表格模拟一下你就懂了

在这个表格中，我们的答案 f(3, 10) 由 21 变成了 22。接下来，我就以 f(3, 10) 为例模拟一下

如果没看懂，就自己照着状态转移方程模拟几遍，总是会看懂的

代码如下：

#include <bits/stdc++.h>
using namespace std;
int a[30005],b[30005],c[30005];
int ans[50000][50000];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=k;i++){
        for(int j=b[i];j<=n;j++){
        ans[i][j]=max(ans[i][j-b[i]]+a[i],ans[i-1][j]);
        }
    }
    cout<<ans[k][n];
    //system("pause");
    return 0;
}

如果你把这个代码直接交上去，会发现编译失败了

这是因为数组开大了，但如果你把数组改小以后，也会RE

于是我们有需要我们的老朋友了——滚动数组

观察上文的转移方程，可以发现 i 没什么用，于是我们可以把 i 去掉，代码见下：

#include <bits/stdc++.h>
using namespace std;
int a[30005],b[30005],c[30005];
int ans[50000];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=k;i++){
        for(int j=b[i];j<=n;j++){ //注意起始条件和终止条件
            ans[j]=max(ans[j-b[i]]+a[i],ans[j]);
        }
    }
    cout<<ans[n];
    //system("pause");
    return 0;
}

不知道你们有没有注意到，这个滚动数组是从 b_i 开始的，这是因为 b_i 以前的数据都是 0，不需要计算。

如果你与前面的代码比较，就会发现这里 j 的起始值和终止条件反了过来，也许你还记得之前的一句话

在这里，我们就是要运用 数据被覆盖 这个东西，来让 i 来重复加入，从而达到第 i 个物品无穷多的的特点。

带附件的背包

以下例题

P1064 [NOIP2006 提高组] 金明的预算方案

在上面的背包问题中，我们的物品只有主件，但在带附件的背包中，我们还会带着一些附件。当我们要 买主件时，不一定要买附件，但如果要买附件，就必须要买主件。 所以我们在 DP 时，就有了更多的选择

接下来，我将用 tai,j 来表示第 i 个物品的第 j 个附件的重量，用 tbi,j 来表示第 i 个物品的第 j 个 附件的价值，用 tci 来表示第 i 个物品的附件的个数

这类题目目的状态转移方程：

在这道题中，附件最多有 2 个，所以状态转移方程为