一本通 2.9.2 动态规划中背包问题

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

　　

　　设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。

　　为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

　　

　　?

　　朴素解法

　　二进制拆分解法

　　单调队列优化方法

　　一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

　　

　　

　　1271：【例9.15】潜水员

　　潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？

　　例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

　　3 36 120

　　10 25 129

　　5 50 250

　　1 45 130

　　4 20 119

　　如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

　　你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

　　

　　一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

　　

　　给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

　　

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

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

　　01背包问题

　　有n个正整数，找出其中和为t(t也是正整数)的可能的组合方式。如：

　　n=5,5个数分别为1,2,3,4,5，t=5；

　　那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。

　　01背包的方案数? 使用sum 初始化边界f[0]=1

　　宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

　　一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而，野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。当小智的精灵球用完时，狩猎也宣告结束。

　　我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。

　　小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。

　　现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

　　01背包的二维费用问题? 最大精灵数的情况情况下代价2最小

　　小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

　　问小明有多少种买书方案？（每种书可购买多本）

　　完全背包问题的方案数? f[j]=f[j]+f[j-a[i]]? 初始条件f[0]=1

　　经典0—1背包问题,有n个物品，编号为i的物品的重量为w[i]，价值为c[i]，现在要从这些物品中选一些物品装到一个容量为m的背包中，使得背包内物体在总重量不超过m的前提下价值尽量大。

　　01背包问题

　　有一个箱子容量为V（正整数，0≤v≤20000），同时有n个物品（0< n ≤30），每个物品有一个体积（正整数）。

　　要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

　　完全背包问题? ?限制为箱子的容量限制下求箱子最大的物品体积，最后结果为V-f[V]

　　信息学院的同学小明毕业之后打算创业开餐馆.现在共有n个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这?n个地点排列在同一条直线上。我们用一个整数序列m1,m2,...m来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi?表示在mi处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。

　　最长上升子序列的变形