自动搬运

查看原文

来自洛谷，原作者为

	llzzxx712 屑大三

搬运于2025-08-24 21:40:50，当前版本为作者最后更新于2019-10-18 13:34:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

想弄懂完全背包题，当然是要先看01背包喽！作为一个刚刚学会背包一个星期的蒟蒻，我决定把我弄懂01背包和完全背包的过程分享给更多蒟蒻。

01背包

题目描述

一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn，求旅行者能获得最大总价值。

【输入】

第一行：两个整数，M (背包容量，M≤200)和N(物品数量，N≤30）

第2..N+1 行：每行二个整数Wi，Ci，表示每个物品的重量和价值。

【输出】

仅一行，一个数，表示最大总价值。

---

下面是01背包模板代码，最下面有样例数据

    #include<iostream>
    using namespace std;
    const int maxm=201,maxn=31;
    int m,n;
    int w[maxn],c[maxn];
    int f[maxn][maxm];//表示前i个物品在容量为v下可以获得的
    最大总价值 
    int main()
    {
      cin>>m>>n;//背包容量m和物品数量n 
      for(int i=1;i<=n;i++){
          cin>>w[i]>>c[i];//输入每个物品的质量和价值 
      }
      for(int i=1;i<=n;i++){
          for(int v=m;v>0;v--){
              if(w[i]<=v){
                 f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
              }
    //f[i][v]表示前i件物品，总体积（质量）不超过v的最优价值 
              else{
                  f[i][v]=f[i-1][v];
              }
          }//个人习惯，每个循环都带括号，方便添加代码
       }
       cout<<f[n][m];//f[n][m]为最优解 
       return 0;
    }

f[i-1][v-w[i]]这东西代表的就是在v的空间下，放入w[i](也就 是第i件物品）后再放之前的物品获得的价值。[v-w[i]]就是现在 的体积减掉该物品体积后剩下的，就是可以前i件物品留下的， 在之前的计算中已经求得了前i件物品可以得到的价值.

它具有自动检索一般的功能，比如样例中我们在i=4时，它根据 [v-w[i]]找到了此时除了它剩下的空间放前面物品最多可以获得3 的价值，再加上它的9的价值得到12。同时它还和只放3个物品进行比较，如果第四个物品价值过小，程序将会选择不拿4。

当我把 输入数据第四个物品和第三个物品的价值改为7时，发现f[3][10] 就已经达到了最大值11，程序在i=4时没有更改结果

以下是通过文件操作打出来的数据

输入:

10 4

2 1

3 3

4 5

7 9

输出： 12

测试输出：

（每段数据有10个，第i段数据代表i等于几时的f[i][1..10],每次的第一个数据代表本次操作时的 v）

10 1

9 1

8 1

7 1

6 1

5 1

4 1

3 1

2 1

1 0

---

10 4

9 4

8 4

7 4

6 4

5 4

4 3

3 3

2 1

1 0

---

10 9

9 9

8 8

7 8

6 6

5 5

4 5

3 3

2 1

1 0

---

10 12

9 10

8 9

7 9

6 6

5 5

4 5

3 3

2 1

1 0

下面是用一维数组实现01背包

（用的本题数据和字母）但本题不是01背包题（因为每个种类中你可以选择若干道题，而不是只能做一道或不做），所以下面代码无法通过

    #include<iostream>
    using namespace std;
    int x,y;
    int t[10002],p[10002];
    int f[10002];
    int main()
    {
        int m,n;
        cin>>m>>n;
        for(int i=1;i<=n;i++){
            cin>>p[i]>>t[i];
        }
        for(int i=1;i<=n;i++){
            for(int t1=m;t1>=t[i];t1--){
                f[t1]=max(f[t1],f[t1-t[i]]+p[i]);
             }
        }
        cout<<f[m];
        return 0;
    }

这里我们可以看到，它省去了数组中用来表示前i个物品（题目）的一维，因为这不重要。我们不需要管它是在前几个物品（题目）中在容量v（时间t）下得到的最大价值（最高分数），我们只需要知道在容量v下可以得到的最大价值。所以现在的f[100002]就是代表在多少容量（时间）下可以得到的最高价值（分数）。其余都和上面的背包模板一样。

---

好，现在就是完全背包了

下面是AC代码

#include<iostream>
    using namespace std;
    int x,y;
    int t[10002],p[10002];
    int f[10002];
    int main()
    {
        int m,n;
        cin>>m>>n;
           for(int i=1;i<=n;i++){
              cin>>p[i]>>t[i];
           }
        for(int i=1;i<=n;i++){
            for(int t1=t[i];t1<=m;t1++){//注意这一行
                f[t1]=max(f[t1],f[t1-t[i]]+p[i]);
            }
        }
        cout<<f[m];
        return 0;
    }

也许没有我的“注意这一行”，你可能找不出来它和上面的01背包代码有什么区别。这也正说明了完全背包和01背包的相似。他们的差别只有第二重for循环的差别。

在01背包中，t1从m一直减到t【i】，保证了每个物品在一个t1中只会被放一次。 而完全背包中，从t1一直加到m，使在可以放下的情况下尽量多地放。