当前位置:首页 >> 教学案例/设计 >>

简单背包问题专题


简单背包问题专题
作者:炉灰 本文内容遵从 CC 版权协议 一:01 背包问题 例题: 例题:纪老师的减肥计划
话说, 一日我们亲爱敬爱可爱的纪老师为了让自己的体型更加完美, 于是乎毅然决然的 加入了减肥大军的行列中来.他打算在 n 小时内将自己的体重从 w 减到尽可能低.纪老师 的减肥方法是不吃饭, 而每个小时不吃饭所能减的体重并不相同. 同样老师因为不吃而下降 的 hp 也不相同. 现在纪老师想让你帮忙求出他的体重最低可以达到多少. (我想大家都不希 望老师饿死吧^_^) 输入格式:第一行有三个数,分别是 n,w,HP.第二行到第 n+1 行每行有两个数,分别表 示该小时不吃饭所减的体重 wi 和下降的 hpi.每个数间用空格隔开. 输出格式:输出一个数,即老师可以达到的最低体重. 样例输入: 4 200 100 14 90 22 10 90 110 3 99 样例输出: 164 解析:此为典型的 01 背包问题,hp 是背包容量,下降体重 wi 是价值,而每个小时吃不吃 饭则是该物品取不取.该类问题用子问题定义状态:即 f[i][v]表示前 i 件物品恰放入一个容 量 为 v 的 背 包 可 以 获 得 的 最 大 价 值 . 则 其 状 态 转 移 方 程 便 是 : f[i][j]=max{f[i-1][j],f[i-1][j-hp[i]]+w[i]}. 用递推的 for 结构实现出来如下,其中用 f[i][j]表示在前 i 个小时有 j 点 hp 所能减的最大体 重. for(i=1;i<=n;i++)// i 代表只考虑前 i 个小时的情况 { for(j=HP;j>=0;j--)// j 表示在前 i 个小时还有 j 点 hp 时 { if ( f[i-1][j]>f[i-1][j-hp[i]]+w[i] )\\ 比较是吃还是不吃是最优 { f[i][j]=f[i-1][j];\\ 不吃的时候体重不变 } else { f[i][j]=f[i-1][j-hp[i]]+w[i];\\ 吃的时候体重下降 } } } 优化空间复杂度 以上方法的时间和空间复杂度均为 O(N*V),其中时间复杂度基本已经不能再优化了,但空 间复杂度却可以优化到 O(V).具体如何实现,请同学们自己想办法解决.

二:完全背包 例题:纪老师贴膏药 例题:
粗心的张彦彬在上一讲中将纪老师得 hp 降到了 0,可怜的老师性命危在旦夕!同学们 必须采取紧急行动来挽救纪老师的生命. 李嘉浩同学飞快的将老师放上的担架, 抬着老师到 了陈司义开的地精商店去贴膏药.商店里有 n 种膏药,有着不同的恢复力与价格.每种膏药 的库存量都很充足,但李嘉浩同学带的钱 m 却有限.请你设计方案将老师的 hp 升到最高. 输入格式:第一行两个数 n,m 分别表示膏药种类和拥有钱的总数.第而行到第 n+1 每行有 两个数,分别表示膏药的价格和恢复 hp 的点数. 输出格式:输出一个数,即纪老师的 hp 的最大值. 输入样例: 4 200 10 1 20 90 99 10 201 8999 输出样例: 900 解析:完全背包与 01 背包唯一的不同就是每一种物品可以去无数次,如本题中就写到膏药 的库存绝对充足,如果没有这句话完全背包就变成了 01 背包问题.也正是由于这一点导致 完全背包与 01 背包的解法惊人的相似. 它的动态方程是 f[i][j]=max{f[i][j],f[i][j-c[i]]+w[i]} 发 现没有,一模一样!那它的解法到底和 01 背包有什么不同呢?请看: for(i=1;i<=n;i++)// i 代表只考虑前 i 种膏药的情况 { for(j=0;j<=HP;j++)// j 表示在前 i 种膏药还有 j 点 money 时 { if ( f[i-1][j]>f[i-1][j-hp[i]]+w[i] )\\ 比较是贴还是不贴是最优 { f[i][j]=f[i-1][j];\\ 不贴的时候 hp 不变 } else { f[i][j]=f[i-1][j-hp[i]]+w[i];\\ 贴的时候 hp 上升 } } } 只是将 j 的循环循序颠倒了一下而已,为什么这样一改就可行呢?首先想想为什么 01 背包中要按照 j=HP..0 的逆序来循环.这是因为要保证第 i 次循环中的状态 f[i][j]是由状态 f[i-1][j-hp[i]]递推而来.换句话说,这正是为了保证每件物品只选一次,保证在考虑"选入 第 i 件物品"这件策略时,依据的是一个绝无已经选入第 i 件物品的子结果 f[i-1][j-hp[i]]. 而现在完全背包的特点恰是每种物品可选无限件,所以在考虑"加选一件第 i 种物品"这种 策略时,却正需要一个可能已选入第 i 种物品的子结果 f[i][j-hp[i]],所以就可以并且必须采 用 j= 0..HP 的顺序循环.这就是这个简单的程序为何成立的道理.

炉灰原创 转载请注明出处


相关文章:
动态规划-背包问题专题_图文.ppt
动态规划-背包问题专题 - 动态规划 - 背包问题及其变形 长沙市一中 曹毅 回
【数据结构实验】简单背包问题.pdf
【数据结构实验】简单背包问题_计算机软件及应用_IT/计算机_专业资料。【数据结构...简单背包问题专题 2页 免费 数据结构实验:二叉树的... 5页 1下载券 数据...
背包问题.txt
背包问题 - 背包问题 译 by 铭 (在中国,背包问题一般是这样描述的:设n个
背包问题九讲.pdf
2.4 转化为 01 背包问题求解 01 背包问题是最基本的背包问题,我们可以考虑把完全背包问题转化为 01 背包问 题来解。 最简单的想法是,考虑到第 i 种物品最多选...
背包问题题目及含义.doc
一个简单有效的优化 完全背包问题有一个很简单有效的优化,是这样的:若两件物品...阅读专题 标题的含义和作... 暂无评价 8页 2下载券 背包旅游者的演变与概...
背包九讲(动态规划的经典入门).txt
背包九讲(动态规划的经典入门) - DD牛的背包九讲 P01: 01背包问题
背包问题九讲(很详细).doc
背包问题九讲(很详细) - P01: 01 背包问题 题目 有 N 件物品和一个
背包问题九讲和源程序(答案).doc
背包问题九讲和源程序(答案) - 背包问题九讲和源程序(答案).txt 台湾一日
动态规划经典案例详解(背包问题).pdf
动态规划经典案例详解(背包问题) - 动态规划经典案例详解之背包问题 【摘要】 本文主要从动态规划经典案例背包问题的动态规划设计思路出发, 结合具体实 例,对...
背包问题九讲.pdf
背包问题九讲 - 背包问题九讲 目录 第一讲 01背包问题 第二讲 完全背包问题 第三讲 多重背包问题 第四讲 混合三种背包问题 第五讲 二维费用的背包问题 第六...
背包问题九讲(很详细).doc
背包问题九讲(很详细) - P01: 01 背包问题 题目 有 N 件物品和一个
noip背包问题教程(背包九讲).doc
3 转化为01背包问题求解既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单 的想法是,考虑到第i种物品最多选V/c[i...
背包问题九讲.doc
多重背包问题 第三讲 多重背包问题每种物品有一个固定的次数上限。 第四讲 混合三种背包问题将前面三种简单的问题叠加成较复杂的问题。 第五讲 二维费用的背包...
背包问题的递归与非递归.txt
背包问题的递归与非递归 - /** 简单背包问题 问题定义: 有一个背包重量是
背包问题_图文.ppt
背包问题 - 背包问题 By Szylover 2012-2-16 szylover 2 一个背包问题的引入 2012-2-16 辰辰是个天资聪颖的孩子,他的梦想是成为世界上 最伟大...
背包问题九讲 2.0.pdf
2.4 转化为01背包问题求解 01背包问题是最基本的背包问题,我们可以考虑把完全背包问题转化为01 背包问题来解。 最简单的想法是,考虑到第i种物品最多选?V /Ci ?...
第9章 第3节 动态规划背包问题(C++版)_图文.ppt
转化为01背包问题求解 既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转 化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选V/w[i]...
背包问题九讲_图文.pdf
背包问题九讲 - 背包问题九讲v1.1 PDF版 2007-7-15 目录 第一
7.20背包问题_图文.ppt
7.20背包问题 - 背包问题的探究 Hu Wenbiao 2010.7.20
01背包问题题解.doc
01背包问题题解 - P01: 01 背包问题 题目 有 N 件物品和一个容量为
更多相关标签: