(HDUACM201303版_07)背包专题

1、ACM程序设计程序设计杭州电子科技大学 刘春英2022-1-122课后作业课后作业，你你 了吗？了吗？都做都做2022-1-123每周一星每周一星（6 6）：）：ray007great2022-1-124第第七七讲讲背包算法背包算法（Knapsack AlgorithmKnapsack Algorithm）2022-1-125导引问题-食堂就餐n现有餐券1张，面值10元n菜肴N种（价格精确到0.1元）：炸鸡腿3元；大排1.5元；荷包蛋：1元；炒青菜：1.2元；番茄炒蛋：2.5元 .n餐券的特点：一次性使用，不找零；n问：若每种菜只挑一个，为了充分发挥餐券的作用，最多可以消费多少元？2022-1

2、-126什么是背包问题n背包的基本模型：给你一个容量为V的背包和若干种物品，在一定的限制条件下（每种物品都占用一定容量），问最多能放进多少价值的物品？2022-1-127关于背包问题n1、最典型、最基本的DP问题；n2、理解并熟练掌握背包问题意义重大；n3、DP问题中“状态”概念的理解；n4、背包的每个容量就是“状态”,选择每个物品就是“状态的决策”；2022-1-128背包问题的分类n01背包n完全背包n多重背包n混合三种背包n二维费用背包n分组背包n有依赖的背包2022-1-129n0101背包背包问题问题: :n最基础的背包问题：最基础的背包问题：有有N N件物品和一个容量为件物品和一个

3、容量为V V的的背包。第背包。第i i件物品的费用是件物品的费用是cici，价值是，价值是wiwi。求解将哪些物品装入背包可使价值总和最大。求解将哪些物品装入背包可使价值总和最大。n问题特点：问题特点：每种物品仅有一件，可以选择放或不每种物品仅有一件，可以选择放或不放，用子问题定义状态：即放，用子问题定义状态：即fivfiv表示前表示前i i件物件物品恰放入一个容量为品恰放入一个容量为v v的背包可以获得的最大价的背包可以获得的最大价值。值。n状态转移方程：状态转移方程：nfiv=maxfi-1v,fi-1v-ci+wifiv=maxfi-1v,fi-1v-ci+wi一、一、0101背包背包2

4、022-1-1210nSample Inputn1n5 10n1 2 3 4 5n5 4 3 2 1nSample Outputn14一、01背包-Bone Collector2022-1-1211一、01背包-Bone Collectorv 问题分解：当前最优解，要么包含第问题分解：当前最优解，要么包含第i i种物品，要么不包含第种物品，要么不包含第i i种物品种物品v DPijDPij表示前表示前i i个物品个物品, ,背包容量为背包容量为j j的最优值。的最优值。v 状态转移方程为：状态转移方程为：v DPij = max(DPi-1j,DPi-1j-vi + wi)DPij = max

5、(DPi-1j,DPi-1j-vi + wi)2022-1-1212n时间复杂度时间复杂度N N* *V , V , 空间复杂度空间复杂度N N* *V Vn空间复杂度优化空间复杂度优化: :只用一位数组只用一位数组DPjDPj来实现；来实现；n但此时，遍历背包的顺序必须但此时，遍历背包的顺序必须反一反反一反, ,想想为什么想想为什么? ?0101背包问题伪代码如下背包问题伪代码如下: :for i = 1 to n /for i = 1 to n /所有物品所有物品 for j = V to vi for j = V to vi dpj = max(dpj , dpj-vi + wi); d

6、pj = max(dpj , dpj-vi + wi);空间优化到一维空间优化到一维V Vn原因：如果顺序遍历原因：如果顺序遍历, ,一种物品会被一种物品会被 取取 好多次好多次一、01背包-Bone Collector2022-1-1213二、完全背包Piggy-Bankn完全背包特点完全背包特点: :一种物品可以取无数个一种物品可以取无数个n可否转化成可否转化成0101背包问题？背包问题？n朴素的转化方式是？朴素的转化方式是？n回忆回忆0101背包为何要对容量按照逆序循环？背包为何要对容量按照逆序循环？n和和0101背包类似背包类似, ,不过就是正着写！不过就是正着写！n这类能不能达到的问

7、题应该怎么实现这类能不能达到的问题应该怎么实现? ?2022-1-1214三、多重背包 珍惜现在，感恩生活n多重多重背包特点背包特点: :n一种物品有一种物品有C C个（既不是固定的个（既不是固定的1 1个，也不是无数个）个，也不是无数个）n最朴素的想法最朴素的想法? ?n优化的方法：优化的方法：n运用神奇的二进制运用神奇的二进制, ,进行物品拆分进行物品拆分, ,转化成转化成0101背包背包n物品拆分物品拆分, ,把把1313个相同的物品分成个相同的物品分成4 4组组(1,2,4,6)(1,2,4,6)n用这用这4 4组可以组成任意一个组可以组成任意一个113113之间的数之间的数! !n原

8、理原理: :一个数总可以用一个数总可以用2k2k表示表示n而且总和等于而且总和等于13,13,所以不会组成超过所以不会组成超过1313的数的数n所以可将一种有所以可将一种有C C个的物品拆分成个的物品拆分成1,2,4,.,2(k-1),C-(2k-1)1,2,4,.,2(k-1),C-(2k-1)n然后进行然后进行0101背包背包2022-1-1215优化部分的参考代码nint t = 1;int t = 1;nwhile (x=t) while (x=t) nvcnt = avcnt = a* *t;t;nccnt+ = bccnt+ = b* *t;t;nx -= t;x -= t;nt

9、= 1;t = 1;n nif (x) if (x) nvcnt = avcnt = a* *x;x;nccnt+ = bccnt+ = b* *x;x;n 2022-1-1216四、混合三种背包n混合混合背包特点背包特点: :n如果将三种背包问题混合起来，也就是说，有的物品只可以取一次如果将三种背包问题混合起来，也就是说，有的物品只可以取一次（0101背包），有的物品可以取无限次（完全背包），有的物品可以背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包），应该怎么求解呢？取的次数有一个上限（多重背包），应该怎么求解呢？nfor i=1.Nfor i=1.Nn

10、 if if 第第i i件物品属于件物品属于0101背包背包n ZeroOnePack(ci,wi) ZeroOnePack(ci,wi)n else if else if 第第i i件物品属于完全背包件物品属于完全背包n CompletePack(ci,wi) CompletePack(ci,wi)n else if else if 第第i i件物品属于多重背包件物品属于多重背包n MultiplePack(ci,wi,ni) MultiplePack(ci,wi,ni)n详见：背包问题九讲详见：背包问题九讲2022-1-1217五、二维费用背包n二维费用二维费用背包问题背包问题: :n对于

11、每件物品，具有两种不同的费用；选择这件物品必须同时付对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容出这两种代价；对于每种代价都有一个可付出的最大值（背包容量），求怎样选择物品可以得到最大的价值。量），求怎样选择物品可以得到最大的价值。n设第设第i i件物品所需的两种代价分别为件物品所需的两种代价分别为aiai和和 bi bi，两种代价可付，两种代价可付出的最大值（两种背包容量）分别为出的最大值（两种背包容量）分别为V V和和U U，物品的价值为，物品的价值为wiwi。n对应算法：对应算法：费用加了一维，只需状态也加一维即可！费用

12、加了一维，只需状态也加一维即可！n设设fivufivu表示前表示前i i件物品付出两种代价分别为件物品付出两种代价分别为v v和和u u时可获得的时可获得的最大价值，状态转移方程则为：最大价值，状态转移方程则为：nfivu=maxfi-1vu,fi-1v-aiu-bi+wifivu=maxfi-1vu,fi-1v-aiu-bi+win详见：背包问题九讲详见：背包问题九讲2022-1-1218六、分组背包n分组分组背包问题背包问题: :nN N件物品和一个容量为件物品和一个容量为V V的背包，第的背包，第i i件物品的费用是件物品的费用是cici，价值是，价值是wiwi。这些物品被分为若干组，每

13、组中的物品互相冲突，最多选一件。求解将哪这些物品被分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使物品的费用总和不超过背包容量，且价值总和最大。些物品装入背包可使物品的费用总和不超过背包容量，且价值总和最大。n对应算法：对应算法：问题变成了每组物品有若干种策略：是选择本组的某一件，问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设还是一件都不选。也就是说设fkvfkv表示前表示前k k组物品花费费用组物品花费费用v v能取得的能取得的最大权值，则有：最大权值，则有：nfkv=maxfk-1v,fk-1v-ci+wi|fkv=maxfk-1v,

14、fk-1v-ci+wi|物品物品i i属于组属于组kkn使用一维数组的伪代码如下：使用一维数组的伪代码如下：nfor for 所有的组所有的组k kn for v=V.0 for v=V.0n for for 所有的所有的i i属于组属于组k kn fv=maxfv,fv-ci+wi fv=maxfv,fv-ci+wi2022-1-1219附录：附录：0101背包参考代码（背包参考代码（26022602）n#include n#include nusing namespace std;nint dp1001, v1000, p1000;ninline int max(int a, int b) return ab?a:b; nint main()nint c;nscanf(%d, &c);nwhile (c-) nint n, V, i, j;nscanf(%d %d, &n, &V);nfor (i=0; in; i+) scanf(%d, &pi);nfor (i=0; in; i+) scanf(%d, &vi);nmemset(dp, 0, sizeof(dp);nfor (i=0; i=vi; j-)ndpj = max(dpj, dpj-vi + pi);n