Level3题解（11-20）

  2. 主页
  4. 文档
  6. Level3题解（11-20）
  8. 第19课 背包问题

第19课 背包问题

01背包和无限背包

❝背包问题是一个经典的动态规划模型。它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题.❞

0/1背包问题

典型题目

有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 c[i]，价值是 w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

每个物品最多只能放一次或者选择不放, 所以是0/1背包问题.

特例:

让我假设现在的背包的容量是 v = 10

物品编号12345
物品体积24397

怎么才能获得最大价值呢?

暴力搜索法，我把伪代码贴上。

if(当前容量>背包容量||枚举的物体>所有物体){
    return;
} else {
    maxV = max(MaxV,nowV);
}
for(枚举的物体){
    递归(A, V, i+1, nowA+A[i], nowV+V[i], m);
}
局限性在于复杂度太高，O(N^2)。

贪心算法 – 可能得到的不是正确解

我们尝试用贪心算法解决问题。

  • 贪心1: 取价值最大
  • 贪心2: 取花销最小的
  • 贪心3: 取性价比最高
  • 贪心4: 随机取值

动规思路

复杂问题简单化.

1 个物品时很好判断出放和不放的价值差别. 背包容积是 1 时 也很好判断出怎么放价值最大.

而多个物品是从1个 1个的物品逐步累加起来的. 背包容积很大时, 也可以看作,小容量背包合在一起来的.

用v[i]表示物品体积，求最多能装多少体积的物品

所以接下来开始动规：

首先定义状态 f[i][j] 以j为容量为放入前i个物品(按i从小到大的顺序)的最大价值，那么i=1的时候，放入的是物品1，这时候肯定是最优的啦！

最大容量, 则其状态转移方程：

f[i][v] = max(f[i-1][v],f[i-1][v-c[i]]+w[i])

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前 i 件物品放入容量为 v 的背包中”这个子问题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只和前 i − 1 件物品相关的问题。

如果不放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入容量为 v 的背包中”，价值为 F[i − 1][v]；

如果放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入剩下的容量为 v − C[i] 的背包中”，此时能获得的最大价值就是 F[i − 1][v − C[i]再加上通过放入第 i 件物品获得的价值 W[i]。

//伪代码
//二维
for(int i=1;i<=n;i++)
{
    for(int v=0; v<=m; v++)
    {
        f[i][v]=f[i-1][v];
        if(v>=v[i])
        f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i]);
    }
}

动规思想

它的设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种==最优化问题==，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

「首先是重叠子问题」，不同的问题，可能都要求1个相同问题的解。假如A经理想知道他下面最优秀的人是谁，他必须知道X,Y,Z,O,P组最优秀的人是谁， 甲总监想知道自己下面最优秀的人是谁，也要去知道X,Y,Z组里面最优秀的人是谁？这就有问题重叠了，两个人都需要了解X,Y,Z三个小组最优秀的人。

「其次是最优子结构」，最优解肯定是有最优的子解转移推导而来，子解必定也是子问题的最优解。甲总监下面最优秀的3个人肯定是从X,Y,Z提交上来的3份名单中选择最优秀的三个人。例如Q哥是X组长下面的第5名，那么他肯定不可能是甲总监下面最优秀的三个。

「第三是无后效性」，这个问题可能比较难理解，也就是求出来的子问题并不会因为后面求出来的改变。我们可以理解为，X组长挑选出三个人，即便到了高级经理选出大部门最优秀的三个人，对于X组来说，最优秀的还是这3个人，不会发生改变。

过程

动态规划问题，大致可以通过以下四部进行解决。

  1. 「划分状态」

即划分子问题，例如上面的例子，我们可以认为每个组下面、每个部门、每个中心下面最优秀的3个人，都是全公司最优秀的3个人的子问题

  1. 「状态表示」

即如何让计算机理解子问题。上述例子，我们可以实用f[i][3]表示第i个人，他手下最优秀的3个人是谁。

  1. 「状态转移」

即父问题是如何由子问题推导出来的。上述例子，每个人大Leader下面最优秀的人等于他下面的小Leader中最优秀的人中最优秀的几个。

  1. 「确定边界」

确定初始状态是什么？最小的子问题？最终状态又是什么。例如上述问题，最小的子问题就是每个小组长下面最优秀的人，最终状态是整个企业，初始状态为每个领导下面都没有最优名单，但是小组长下面拥有每个人的评分。

空间优化

以上方法的时间和空间复杂度均为 O(V N)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到 O(V )。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环 i: 1->N，每次算出来二维数组 F [i, 0 … V ] 的所有值。那么，如果只用一个数组 F [0 … V ]，能不能保证第 i 次循环结束后 F[v] 中表示的就是我们定义的状态 F[i][v] 呢？

F [i][ v] 是由 F[i − 1][v] 和 F [i − 1][v − Ci] 两个子问题递推而来，能否保证在推 F[i][v] 时（也即在第 i 次主循环中(推 F[v] 时) 能够取用 F[i − 1][v] 和 F[i − 1][v − Ci] 的值呢？

事实上，这要求在每次主循环中我们以 v … 0 的递减顺序计算 F[v]，这样才能保证计算 F[v] 时 F[v − Ci] 保存的是状态 F[i − 1][v − Ci] 的值。伪代码如下：

// 一维数组优化
for(int i=1; i<=n; i++)
{
    for(int v=m; v>=c[i]; v--)
    {
        f[v]=max(f[v], f[v-c[i]] + w[i]);
    }
}

P1048 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 2 个整数 T（1≤T≤1000）和 M（1≤M≤100），用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。

接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

输入输出样例

  • 输入 #1复制
70 3
71 100
69 1
1 2
  • 输出 #1复制

3

说明/提示

【数据范围】

对于 30% 的数据，M≤10；对于全部的数据，M≤100。

【题目来源】

NOIP 2005 普及组第三题

参考代码

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

int t, m;
int a[102], v[102];
int f[10002];

int main()
{
 scanf("%d %d", &t, &m);
 for(int i=1; i <=m; i++) {
  scanf("%d %d", &a[i], &v[i]);
 }

 for(int i = 1; i <= m; i++)
  for(int j = t; j >= a[i]; j--) {
    f[j] = max(f[j], f[j-a[i]] + v[i]);
 }

 printf("%d", f[t]);

 return 0;
}

初始化细节

有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别 这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了 ==F[0] 为 0==，其它 ==F[1…V ] 均设为-∞==，这样就可以保证最终得到的 F[V] 是一种恰好装满背包的最优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 ==F[0…V]全部设为 0==。

这是为什么呢？

可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。

这个小技巧完全可以推广到其它类型的背包问题，后面不再对进行状态转移之前的初始化进行讲解

小结

01 背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思 想。另外，别的类型的背包问题往往也可以转换成 01 背包问题求解。故一定要仔细体 会上面基本思路的得出方法，状态转移方程的意义，以及空间复杂度怎样被优化。

完全背包问题

  • 题目:

有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品 的费用是 Ci，价值是 Wi。求解：将哪些物品装入背包，可使这些物品的耗费的费用总 和不超过背包容量，且价值总和最大。

基本思路

这个问题非常类似于 01 背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2 件……直至取 ⌊V /Ci⌋ 件等许多种。

状态转移:

f[i][v]=max(f[i-1][v-k*c[i]]+k*w[i] | 0<=k*c[i]<=v)
for(int i = 1; i <= n; i++)
{
    for(int j = 0; j <= m; j++)
    {
        for(int k = 0; k <= count[i]; ++ k) {
            // 枚 举 要 放 进 去 的 数 量
            if(v >= k * v[i])
                f[i][v]= max(f[i-1][v], f[i-1][v- k*c[i]] + k * w[i]);
         }
    }
}

优化

  • 完全背包问题有一个很简单有效的优化，是这样的：若两件物品 i、 j 满足 Ci ≤ Cj 且 Wi ≥ Wj，则将可以将物品 j 直接去掉，不用考虑。
  • 首先将费用大于 V 的物品去掉

算法

for(int i = 1; i <= n; i++)
{
    for(int v = c[i]; v <= m; v++)
    {
        f[v]=max(f[v], f[v-c[i]] + w[i]);
    }
}

为什么这个算法就可行呢？首先想想为什么 01 背包中要按照 v 递减的次序来循环。让 v 递减是为了保证第 i 次循环中的状态 F[i, v] 是由状态 F[i − 1, v − Ci] 递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第 i 件物品”这件策略时，依据的是一个绝无已经选入第 i 件物品的子结果 F[i − 1; v − Ci]。

而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物品”这种策略时， 却正需要一个可能已选入第 i 种物品的子结果 F[i; v − Ci]，所以就可以并且必须采用 v 递增的顺序循环。这就是这个简单的程序为何成立的道理。值得一提的是，上面的伪代码中两层 for 循环的次序可以颠倒。这个结论有可能会 带来算法时间常数上的优化。

小结

完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程。

例题 2 P1616 疯狂的采药

题目背景

此题为纪念 LiYuxiang 而生。

题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

  1. 每种草药可以无限制地疯狂采摘。
  2. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 t 和代表山洞里的草药的数目 m。

第 2 到第 (m + 1) 行，每行两个整数，第 (i + 1) 行的整数  分别表示采摘第 i 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入输出样例

  • 输入 #1复制
70 3
71 100
69 1
1 2
  • 输出 #1复制

140

说明/提示

数据规模与约定

对于 30% 的数据，保证 。

对于 100% 的数据，保证 ， ，且  ，

分析

无限背包

参考代码

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

int t, m;
int a[10002], v[10002];
int f[100002];

int main()
{
 scanf("%d %d", &t, &m);
 for(int i=1; i <=m; i++) {
  scanf("%d %d", &a[i], &v[i]);
 }

 for(int i = 1; i <= m; i++)
  for(int j = a[i]; j <= t; j++) {
    f[j] = max(f[j], f[j-a[i]] + v[i]);
 }

 printf("%d", f[t]);

 return 0;
}

P1802 5倍经验日

题目背景

现在乐斗有活动了！每打一个人可以获得5倍经验！absi2011却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。

题目描述

现在absi2011拿出了x个迷你装药物(嗑药打人可耻….)，准备开始与那些人打了

由于迷你装一个只能管一次，所以absi2011要谨慎的使用这些药，悲剧的是，没到达最少打败该人所用的属性药了他打人必输>.<所以他用2个药去打别人，别人却表明3个药才能打过，那么相当于你输了并且这两个属性药浪费了。

现在有n个好友，有输掉拿的经验、赢了拿的经验、要嗑几个药才能打过。求出最大经验（注意，最后要乘以5）

输入格式

第一行两个数，n和x

后面n行每行三个数，分别表示输了拿到的经验(lose[i])、赢了拿到的经验(win[i])、打过要至少使用的药数量(use[i])。

输出格式

一个整数，最多获得的经验

输入输出样例

  • 输入 #1复制
6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2
  • 输出 #1复制

1060

说明/提示

【Hint】

五倍经验活动的时候，absi2011总是吃体力药水而不是这种属性药>.<

【数据范围】

对于10%的数据，保证x=0

对于30%的数据，保证n<=10,x<=20

对于60%的数据，保证n<=100,x<=100, 10<=lose[i], win[i]<=100,use[i]<=5

对于100%的数据，保证n<=1000,x<=1000,0<lose[i]<=win[i]<=1000000,0<=use[i]<=1000

【题目来源】

fight.pet.qq.com

absi2011授权题目

分析

状态定义: f[i] 表示用 i 瓶药获得的最多经验。

状态转移:

当 i >= use 时，可以选择打败或者不打败

f[i] = max(f[i]+lose, f[i-use]+win)。

当 i < use 时，无法战胜对方。

f[i]+=lose

参考代码

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

const int MAXN = 1006;
int lose[MAXN], win[MAXN], use[MAXN];
long long f[MAXN];
int n, x;

int main()
{
 scanf("%d %d", &n, &x);
 for(int i = 1; i <= n; i++) {
  scanf("%d %d %d", &lose[i], &win[i], &use[i]);
 }

 for(int i = 1; i <= n; i++) {
  for(int v = x; v >= use[i]; v--) {
   f[v] = max(f[v] + lose[i], f[v-use[i]] + win[i]);
  }

  for(int v = use[i] - 1; v >= 0; v--)
          f[v] += lose[i];
 }

 printf("%lld", f[x] * 5);
 return 0;
}

总结

  • 01背包
// 一维数组优化
for(int i=1; i<=n; i++)
{
    for(int v=m; v>=c[i]; v--)
    {
        f[v]=max(f[v], f[v-c[i]] + w[i]);
    }
}
  • 无限背包
for(int i = 1; i <= n; i++)
{
    for(int v = c[i]; v <= m; v++)
    {
        f[v]=max(f[v], f[v-c[i]] + w[i]);
    }
}

题单

  • P1049 装箱问题
  • P1048 采药
  • P1164 小A点菜
  • P1926 小书童——刷题大军
  • P1060 开心的金明
  • P1616 疯狂的采药
  • P1855 榨取kkksc03