蛮力法、动态规划法 求解01背包问题
第八章《算法设计与分析》实验报告
班级：******* 学号：********** 姓名：*****
一、实验内容：
分别用蛮力法、动态规划法求解0/1背包问题。
二、所用算法的基本思想及复杂度分析：
1、蛮力法
1) 基本思想: Exhaustiving all the combinations of the items, then
calculating the maximum values of the items what is not exceed the knapsack capacity value.
2) 复杂度分析:2n
2、动态规划法
1)基本思想:Dynamic programming is a technique for solving problems with
overlapping subproblems.The function:
V(i,0)=V(0,j)=0; (1)
V(i-1,j) j V(i,j)= (2) max{V(i-1,j),V(i-1,j-wi)+vi} j>=w 2)复杂度分析：2n 三、程序伪码： (1)Brute Force: Algorithm MFKnapsack(capacity, values, weights, n) // Input: A nonnegative integer n indicating the number of the frist items being //considered and a nonnegative integer capacity indicating the knapsack’s capacity, A array values[] indicating the values of items, A array weights[] indicating the weights of items. //Output: The value of an optimal feasible subset of the first i items if d== c.size() for (int i = 0; i != d; ++i) if c[i] == 1 cur_weight += weights[i]; cur_value += values[i]; if cur_weight <= capacity && cur_value > max_value max_value cur_value; return; (2)Dynamic Programming: Algorithm MFKnapsack(i,j) //Implements the memory function method for the knapsack problem //Input: A nonnegative integer i indicating the number of the frist items being //considered and a nonnegative integer j indicating the knapsack’s capacity //Output: The value of an optimal feasible subset of the first i items //Note: Uses as global variables input arrays Weights[1..n],Values[1..n],and table //V[0..n,0..w] whose entries are initialized with -1’s except for row 0 and column 0 //initialized with 0’s if V[i,j]<0 if j< Weights[i] value←MFKnapsack(i-1,j) else value←max(MFKnapsack(i-1,j),Values[i]+ MFKnapsack(i-1,j- Weights[i])) V[i,j]←value return V[i,j] 四、源程序及注释： (1)Brute Force： #include #include using namespace std; void MFKnapsack(int capacity, int *values, int *weights, vector { if (d== c.size()) { int cur_weight = 0, cur_value = 0; for (int i = 0; i != d; ++i) { if (c[i] == 1) { cur_weight += weights[i]; cur_value += values[i]; } } if (cur_weight <= capacity && cur_value > max_value) { max_value = cur_value; } return; } c[d] = 0; MFKnapsack(capacity, values, weights, c, d + 1, max_value); c[d] = 1; MFKnapsack(capacity, values, weights, c, d + 1, max_value); } int MFKnapsack(int capacity, int *values, int *weights, int n) { int max_value=0; vector MFKnapsack(capacity,values,weights,c,0,max_value); return max_value; } int main() { int capacity=10,n=7; int values[]={6,3,5,4,6,3,10}; int weights[]={1,2,5,5,4,4,6}; cout << MFKnapsack(capacity, values, weights, n) << endl; return 0; } (2)Dynamic Programming #include #include int v[10][100];//对应每种情况的最大价值 int MFknapsack(int m,int n) { int i,j,weigths[10],values[10]; cout<<"请输入每个物品的重量："< for(i=1;i<=n;i++) cin>>weigths[i]; cout<<"请输入每个物品的价值："< for(i=1;i<=n;i++) cin>>values[i]; for(i=0;i<10;i++) for(j=0;j<100;j++) v[i][j]=0;//初始化数组 for(i=1;i<=n;i++)//递归 for(j=1;j<=m;j++) { if(weigths[i]<=j) //如果当前物品的容量小于背包容量 { if(values[i]+v[i-1][j-weigths[i]]>v[i-1][j]) v[i][j]=values[i]+v[i-1][j-weigths[i]]; else v[i][j]=v[i-1][j]; } else v[i][j]=v[i-1][j]; } return v[n][m]; } int main() { int m,n;int i,j; cout<<"请输入背包的承重量:"< cin>>m; cout<<"请输入物品的总个数:"< cin>>n; cout<<"旅行者背包能装的最大总价值为:"< return 0; } 五、运行输出结果： (1)Brute Force： (2)Dynamic Programming： 0-1背包动态规划解决问题 一、问题描述： 有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？ 二、总体思路： 根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。 原理： 动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。 过程： a) 把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第i个物品选或不选），V i表示第i个物品的价值，W i表示第i个物品的体积（重量）； b) 建立模型，即求max(V1X1+V2X2+…+VnXn)； c) 约束条件，W1X1+W2X2+…+WnXn 《算法分析与设计》 课程实验 专业年级：信息与计算科学 学生学号： 学生姓名： 实验题目：用贪婪法求解背包问题 指导老师： 实验时间：20xx年xx月x日 一、实验内容 用贪婪法求解背包问题 要求：用非递归实现 二、实验步骤 2.1、理解算法思想和问题要求； 2.2、写出每个操作的算法 非递归算法： greedbag() { int N; int c; int[] w; int[] v; Scanner scan=new Scanner(System.in); System.out.print("输入背包的容量:"); c=scan.nextInt(); System.out.print("输入物品的数量:"); N=scan.nextInt(); System.out.print("分别输入物品的价值:"); v=new int[N]; for(int i=0;i 动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。 比如01背包问题。 因为背包最大容量M未知。所以，我们的程序要从1到M一个一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。 测试数据： 10,3 3,4 4,5 5,6 c[i][j]数组保存了1,2,3号物品依次选择后的最大价值. 这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为 4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排c3的最佳方案是4.所以。 总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.) 从以上最大价值的构造过程中可以看出。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗? 下面是实际程序: #include 算法分析与设计实验报告 第 4 次实验 } 附录：完整代码 #include 01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。 01背包的状态转换方程f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] } f[i,j]表示在前i件物品中选择若干件放在承重为j 的背包中，可以取得的最大价值。 Pi表示第i件物品的价值。 决策：为了背包中物品总价值最大化，第i件物品应该放入背包中吗？ 题目描述： 有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最 首先要明确这张表是从右到左,至底向上生成的。 为了叙述方便，用e10单元格表示e行10列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为10的背包，那么这个背包的最大价值是6，因为e物品的重量是4，背包装的了，把e装进去后价值为6。然后是e9单元格表示背包承重9，只有物品e, e装进去后，背包价值为6，接着是e8, e7单元格，一直到e3单元格表示背包承重3，但物品e承重4，装不了，所以e3=0, 对于d10单元格，表示只有物品e，d时,承重为10的背包,所能装入的最大价值，是10，因为物品e,d这个背包都能装进去。对于承重为9的背包，d9=10,是怎么得出的呢？ 根据01背包的状态转换方程，需要考察两个值， 一个是f[i-1,j],对于这个例子来说就是e9的值6，另一个是f[i-1,j-Wi]+Pi； 在这里， f[i-1,j]表示我有一个承重为9的背包，当只有物品e可选时，这个背包能装入的最大价值 f[i-1,j-Wi]表示我有一个承重为4的背包（等于当前背包承重减去物品d的重量），当只有物品e可选时，这个背包能装入的最大价值 f[i-1,j-Wi]就是指单元格e4值为6，Pi指的是d物品的价值，即4 由于f[i-1,j-Wi]+Pi = 6 + 4 = 10 大于f[i-1,j] = 6，所以物品d应该放入承重为9的背包，所以d9=10. 背包问题贪心法 实验报告 学院：计算机科学与技术学院班级：**** 学号：**** 姓名：**** 一、实验目的 1）以背包问题为例，掌握贪心法的基本设计策略。 2）熟练掌握各种贪心策略情况下的背包问题的算法并实现；其中：量度标准分别取：效益增量P 、物品重量w 、P/w 比值； 3) 分析实验结果来验证理解贪心法中目标函数设计的重要性。 二、问题基本思想描述 (1)贪心法的基本思路 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 （2）背包问题的描述 已知有n 种物品和一个可容纳M 重量的背包，每种物品i 的重量为i w 。假定将物品i 的一部分 i x 放入背包就会得到 i i x p 的效益，这里， 1 0≤≤i x , >i p 。 显然，由于背包容量是M ，因此，要求所有选中要装入背包的物品总重量不得超过M.。如果这n 件物品的总重量不超过M ，则把所有物品装入背包自然获得最大效益。现需解决的问题是，在这些物品重量的和大于M 的情况下，该如何装包，使得得到更大的效益值。由以上叙述，可将这个问题形式表述如下： 极 大 化目标函数 ∑≤≤n i i x p 1i 约束条件 M x w n i i ≤∑ ≤≤1i n i w p x i i i ≤≤>>≤≤1,0,0,10 （3）用贪心策略求解背包问题 首先需确定最优的量度标准。这里考虑三种策略： 关于求解0/1背包问题的动态规划算法 摘要：本文通过研究动态规划原理，提出了根据该原理解决０／１背包问题的方法与算法实现， 并对算法的正确性作了验证．观察程序运行结果，发现基于动态规划的算法能够得到正确的决策方案且比穷举法有效． 关键字：动态规划；０／１背包；约束条件；序偶；决策序列；支配规则 1、引 言 科学研究与工程实践中，常常会遇到许多优化问题，而有这么一类问题，它们的活动过程可以分为若干个阶段，但整个过程受到某一条件的限制。这若干个阶段的不同决策的组合就构成一个完整的决策。0/1背包问题就是一个典型的在资源有限的条件下，追求总的收益最大的资源有效分配的优化问题。 对于0/1背包问题，我们可以这样描述：设有一确定容量为C 的包及两个向量C ’=（S 1，S 2，……，S n ）和P=（P 1，P 2，……，P N ），再设X 为一整数集合，即X=1，2，3，……，N ，X 为SI 、PI 的下标集，T 为X 的子集，那么问题就是找出满足约束条件∑S i 〈=C ，使∑PI 获得最大的子集T 。在实际运用中，S 的元素可以是N 个经营项目各自所消耗的资源，C 可以是所能提供的资源总量，P 的元素可是人们从各项项目中得到的利润。 0/1背包问题是工程问题的典型概括，怎么样高效求出最优决策，是人们关心的问题。 2、求解问题的动态规划原理与算法 2．1动态规划原理的描述 求解问题的动态规划有向前处理法向后处理法两种，这里使用向前处理法求解0/1背包问题。对于0/1背包问题，可以通过作出变量X 1，X 2，……，X N 的一个决策序列来得到它的解。而对于变量X 的决策就是决定它是取0值还是取1值。假定决策这些X 的次序为X n ，X N-1，……，X 0。在对X 0做出决策之后，问题处于下列两种状态之一：包的剩余容量是M ，没任何效益；剩余容量是M-w ，效益值增长了P 。显然，之后对X n-1，Xn-2，……，X 1的决策相对于决策X 所产生的问题状态应该是最优的，否则X n ，……，X 1就不可能是最优决策序列。如果设F j （X ）是KNAP （1，j ，X ）最优解的值，那么F n （M ）就可表示为 F N （M ）=max(f n (M),f n-1(M-w n )+p n )} （1） 对于任意的f i (X),这里i>0，则有 f i (X)=max{f i-1(X),f i-1(X-w i )+p i } （2） 为了能由前向后推而最后求解出F N （M ），需从F 0（X ）开始。对于所有的X>=0,有F 0（X ）=0，当X<0时，有F 0（X ）等于负无穷。根据（2），可求出0〈X 〈W 1和X 〉=W 1情况下F 1（X ）的值。接着由（2）不断求出F 2，F 3，……，F N 在X 相应取值范围内的值。 2．2 0/1背包问题算法的抽象描述 (1)初始化各个元素的重量W[i]、效益值P[i]、包的最大容量M ； (2)初始化Ｓ0； (3)生成S i ； 算法设计与分析期末论文 题目用贪心法求解“0-1背包问题”专业计算机科学与技术 班级09计算机一班 学号0936021 姓名黄帅 日期2011年12月28日 一、0-1背包问题的算法设计策略分析 1.引言 对于计算机科学来说，算法的概念是至关重要的，例如，在一个大型软件系统的开发中，设计出有效的算法将起决定性的作用。算法是解决问题的一种方法或一个过程。程序是算法用某种设计语言具体实现描。计算机的普及极大的改变了人们的生活。目前，各行业、各领域都广泛采用了计算机信息技术，并由此产生出开发各种应用软件的需求。为了以最小的成本、最快的速度、最好的质量开发出适合各种应用需求的软件，必须遵循软件工程的原则。设计一个高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的素算法，这正是计算机科学领域数据结构与算法设计所研究的主要内容。 2. 算法复杂性分析的方法介绍 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N 、I 和A 表示算法要解问题的规模、算法的输入和算法本身，而且用C 表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T 和S 来表示，则有： T=T(N,I)和S=S(N,I) 。（通常，让A 隐含在复杂性函数名当中 最坏情况下的时间复杂性： 最好情况下的时间复杂性： 平均情况下的时间复杂性： 其中DN 是规模为N 的合法输入的集合；I*是DN 中使T(N, I*)达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I 的概率。 算法复杂性在渐近意义下的阶： 渐近意义下的记号：O 、Ω、θ、o 设f(N)和g(N)是定义在正数集上的正函数。 O 的定义：如果存在正的常数C 和自然数N0，使得当N ≥N0时有f(N)≤Cg(N)，则称函数f(N)当N 充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。即f(N)的阶不高于g(N)的阶。 根据O 的定义，容易证明它有如下运算规则： (1)O(f)+O(g)=O(max(f,g))； (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg)； (4)如果g(N)=O(f(N))，则O(f)+O(g)=O(f)； (5)O(Cf(N))=O(f(N))，其中C 是一个正的常数； ∑∈= N D I I N T I P (N)T ),()(avg ∑∑∈==N D I k i i i I N e t I P ),()(1),(min min I N T (N)T N D I ∈=),(min 1I N e t k i i i D I N ∑=∈=)~,(1I N e t k i i i ∑==)~,(I N T =),(max max I N T (N)T N D I ∈=),(max 1I N e t k i i i D I N ∑=∈=),(*1I N e t k i i i ∑==) ,(*I N T = 0/1背包问题动态规划详解及C++代码 1. 问题描述 给定一个载重量为C的背包 有n个物品 其重量为wi 价值为vi 1<=i<=n 要求:把物品装入背包 并使包内物品价值最大2. 问题分析 在0/1背包问题中 物体或者被装入背包 或者不被装入背包 只有两种选择。循环变量i j意义 前i个物品能够装入载重量为j的背包中 数组c意义 c[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值 若w[i]>j 第i个物品不装入背包 否则 若w[i]<=j且第i个物品装入背包后的价值>c[i-1][j] 则记录当前最大价值 替换为第i个物品装入背包后的价值 其c++代码如下 #include 动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇 一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会 有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目 标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 实验四“0-1”背包问题 一、实验目的与要求 熟悉C/C++语言的集成开发环境； 通过本实验加深对贪心算法、动态规划算法的理解。 二、实验内容: 掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题的求解方法，并分析其优缺点。 三、实验题 1.“0-1”背包问题的贪心算法 2.“0-1”背包问题的动态规划算法 说明：背包实例采用教材P132习题六的6-1中的描述。要求每种的算法都给出最大收益和最优解。 设有背包问题实例n=7，M=15,，(w0,w1,。。。w6)=（2,3,5,7,1,4,1），物品装入背包的收益为：（p0，p1，。。。，p6）=（10,5,15,7,6,18,3）。求这一实例的最优解和最大收益。 四、实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。 五、实验程序 // 贪心法求解 #include 0/1 背包问题动态规划详解及C代码 动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。 问题描述： 给定N中物品和一个背包。物品i的重量是W i,其价值位V i，背包的容量为C。问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？？ 在选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能讲物品i 装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题。 问题分析：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) j 0-1背包问题举例： 设n=6，c=20， w={4，5，3，8，6，10}, v={20，10，8，18，15，12} 解： p[7]={(0,0)} q[7]=p[7]⊕(10,12)={ (10,12)} p[6]={(0,0), (10,12)} q[6]=p[6]⊕(6,15)={ (6,15),(16, 27)} p[5]= {(0,0), (6,15),(16, 27)} q[5]=p[5]⊕(8,18)={ (8,18),(14, 33)} p[4]= {(0,0), (6,15), (8,18),(14, 33) } q[4]=p[4]⊕(3,8)={(3,8),(9,23),(11,26),(17, 41)} p[3]= {(0,0),(3,8),(6,15),(8,18),(9,23),(11,26),(14, 33),(17, 41)} q[3]=p[3]⊕(5,10)={(5,10),(8,18),(11,25),(13, 28),(14,33),(16,36),(19, 43)} p[2]= {(0,0),(3,8),(5,10),(6,15),(8,18),(9,23),(11,26),(13, 28),(14, 33),(16,36),(17, 41),(19,43)} q[2]=p[2]⊕(4,20)={(4,20),(7,28),(9,30),(10,35),(12,38),(13,43),(15,46),(17, 48),(18, 53),(20,56)} p[1]={(0,0),(3,8),(4,20),(7,28),(9,30),(10,35),(12,38),(13,43),(15,46),(17, 48),(18, 53),(20,56)} 构造最优解： X={1，1，1，1 实验五应用贪心算法求解背包问题 学院：计算机科学与技术专业：计算机科学与技术 学号：班级：姓名： 、 实验内容： 背包问题指的是：有一个承重为W的背包和n个物品，它们各自的重量和价值分别是n ，假设W w i和v i（1 i n）w i 1i，求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。 二、算法思想： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 三、实验过程： #in elude { float p; // 物品效益 float w; // 物品重量 float X; // 物品该放的数量 int flag; // 物品编号 };// 物品信息结构体 void Insertionsort(goodinfo goods[],int n)// 插入排序，按pi/wi 价值收益进行排序，一般教材上按冒泡排序 { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].p>goods[i].p) { } goods[i+1]=goods[0]; } }// 按物品效益，重量比值做升序排列goods[i+1]=goods[i]; i--; void bag(goodinfo goods[],float M,int n) { float cu; int i,j; 算法设计与分析 项目名称：用蛮力法、动态规划法和贪心法求解0/1背包问题 作者姓名：余武丹 李红波 刘红梅 完成日期：2013年9月20日 目录 第一章：简介（Introduction） 第二章：算法定义（Algorithm Specification） 第三章：测试结果（Testing Results） 第四章：分析和讨论 第一章：简介（Introduction ） 0/1背包问题是给定n 个重量为{w 1, w 2, … ,wn }、价值为{v 1, v 2, … ,vn }的物品和一个容量为C 的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。 在0/1背包问题中，物品i 或者被装入背包，或者不被装入背包，设xi 表示物品i 装入背包的情况，则当xi =0时，表示物品i 没有被装入背包，xi =1时，表示物品i 被装入背包。根据问题的要求，有如下约束条件和目标函数： 于是，问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X =(x 1, x 2, …, xn )。 背包的数据结构的设计： typedef struct object { int n;//物品的编号 int w;//物品的重量 int v;//物品的价值 }wup; wup wp[N];//物品的数组，N 为物品的个数 int c;//背包的总重量 第二章：算法定义（Algorithm Specification ） 1、蛮力法 蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。 用蛮力法解决0/1背包问题，需要考虑给定n 个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。 所以蛮力法解0/1背包问题的关键是如何求n 个物品集合的所有子集，n 个物品的子集有2的n 次方个，用一个2的n 次方行n 列的数组保存生成的子集，以下是生成子集的算法： void force(int a[][4])//蛮力法产生4个物品的子集 { int i,j; int n=16; int m,t; for(i=0;i<16;i++) ????? ≤≤∈≤∑=) 1(}1,0{1 n i x C x w i n i i i （式1） ∑=n i i i x v 1 max （式2） 0/1背包问题动态规划详解及C代码 动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。 比如01背包问题。 /*一个旅行者有一个最多能用M公斤的背包，现在有N件物品， 它们的重量分别是W1，W2，...,Wn, 它们的价值分别为P1,P2,...,Pn. 若每种物品只有一件求旅行者能获得最大总价值。 输入格式： M,N W1,P1 W2,P2 ...... 输出格式： X*/ 因为背包最大容量M未知。所以，我们的程序要从1到M一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。 测试数据： 10,3 3,4 4,5 5,6 c[i][j]数组保存了1,2,3号物品依次选择后的最大价值. 这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放 4."这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放 4."假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为 4."而背包容量为5的时候，则最佳方案为自己的重量 5."背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排c3的最佳方案是 4."所以。总的最佳方案是5+4为 9."这样.一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的 6."而是上一排的 9."说明这时候3号物品没有被选.选的是1,2号物品.所以得 9.") 从以上最大价值的构造过程中可以看出。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗? 下面是实际程序（在VC 6."0环境下通过）: #include 动态规划法求解0-1背包问题 一、动态规划法的设计思想 动态规划法是数学--“运筹学”中一个决策分析的实现，广泛运用在计算机算法、企业决策、市场营销等领域 动态规划法是将待求解的问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经过分解的子问题往往不是独立的。若用分治法求解这类问题，则相同的子问题会被求解多次，以至于最后解决问题需要消耗指数级别的时间。然而，不同子问题的数目常常只有多项式量级。如果能够保存已经解决的子问题的答案，在需要时再找出已经求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以使用个表来记录已经解决子问题的答案，不管子问题以后是否被用到，只要它计算过，就将其结果填入表中，这就是动态规划法的基本思路 动态规划算法通常用于求解具有某种最优性质的问题。这类问题中，可能会有许多可行的解，每个解对应个值，我们希望找到最大值或者最小值的那个解，其步骤如下： 1、找出最优值的性质，并分析其结构特征 2、递归定义最优解的值 3、自底向上的方式计算出最优值 4、根据计算最优值得到的信息，构造一个最优解 步骤1—2是基本步骤，在只需求出最优值的情况下步骤4可以省略。若需要求子问题的最优解，则必须执行步骤4，此时在步骤3中计算最优值时，通常记录等多的信息，以便在步骤4中根据所记录的信息快速构造出一个最优解 动态规划算法是非常有效的算法技术，那么什么时候使用它呢？或者说其运用场景是什么？若求解问题具有一下性质，可以考虑使用动态规划法： 1、最优子结构：如果一个问题的最优解中包含其子问题的最优解，就是说该问题具有最优 子结构。这时候贪婪算法可能也使用求解此类问题 2、重叠子问题：重叠子问题是指用来求解问题的递归算法可以反复的解同样的问题，而不 是总在产生新的问题，即当一个递归算法不断的调用同一个问题时，就说该问题包含重叠子问题，此时若使用分治法递归求解时，则每次遇到子问题都会视为新问题，会极大降低效率，而动态规划法对每个子问题仅计算一次，把解保存到在一个需要时就可以查看的表中 二、动态规划法案例：0-1背包问题 有n个物品，第i个物品的价值为Vi，重量为Wi，其中Vi和Wi均为非负数，背包容量为W，W为非负数。现考虑如何选择装入背包的物品，使装入背包的物品总价值最大。假设商品有5件，n=5，容量为17，W=17 （一）、求解思路 1、使用矩阵规划出最优解 把求解过程看作是一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入 动态规划之-0-1背包问题及改进 有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。在选择装入背包的物品时，对于每种物品i，只能选择装包或不装包，不能装入多次，也不能部分装入，因此成为0-1背包问题。 形式化描述为：给定n个物品，背包容量C >0,重量第i件物品的重量w[i]>0, 价值v[i] >0 , 1≤i≤n.要求找一n元向量(X1,X2,…,X n,), X i∈{0,1}, 使得∑（w[i] * Xi）≤C,且∑ v[i] * Xi达最大.即一个特殊的整数规划问题。 数学描述为： 求解最优值： 设最优值m(i,j)为背包容量为j、可选择物品为i，i+1，……，n时的最优值(装入包的最大价值)。所以原问题的解为m(1，C) 将原问题分解为其子结构来求解。要求原问题的解m(1，C)，可从m(n，C)，m(n-1，C)，m(n-2，C).....来依次求解，即可装包物品分别为（物品n）、（物品n-1，n）、（物品n-2，n-1，n）、……、（物品1，物品2，……物品n-1，物品n）。最后求出的值即为最优值m(1，C)。 若求m(i,j)，此时已经求出m(i+1,j)，即第i+1个物品放入和不放入时这二者的最大值。 对于此时背包剩余容量j=0,1,2,3……C，分两种情况： (1)当w[i] > j，即第i个物品重量大于背包容量j时，m(i,j)=m(i+1,j) (2)当w[i] <= j，即第i个物品重量不大于背包容量j时，这时要判断物品i放入和不放入对m的影响。 若不放入物品i，则此时m(i,j)=m(i+1,j) 若放入物品i，此时背包 0/1背包问题 1. 问题描述 给定一个载重量为m，n个物品，其重量为w i，价值为v i，1<=i<=n，要求:把物品装入背包，并使包内物品价值最大 2. 问题分析 在0/1背包问题中，物体或者被装入背包，或者不被装入背包，只有两种选择。 循环变量i，j意义：前i个物品能够装入载重量为j的背包中 (n+1)*(m+1)数组value意义：value[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值 若w[i]>j，第i个物品不装入背包 否则，若w[i]<=j且第i个物品装入背包后的价值>value[i-1][j]，则记录当前最大价值（替换为第i个物品装入背包后的价值） 计算最大价值的动态规划算法如下： //计算 for(i=1;i if(w[i]<=j && temp>value[i][j]) value[i][j]=temp; } } 即该段程序完成以下n个阶段： 1：只装入1个物品，确定在各种不同载重量的背包下，能够得到的最大价值 2：装入2个物品，确定在各种不同载重量的背包下，能够得到的最大价值 。。。 n：以此类推，装入n个物品，确定在各种不同载重量的背包下，能够得到的最大价值3. 问题求解 确定装入背包的具体物品，从value[n][m]向前逆推： 若value[n][m]>value[n-1][m]，则第n个物品被装入背包，且前n-1个物品被装入载重量为m-w[n]的背包中 否则，第n个物品没有装入背包，且前n-1个物品被装入载重量为m的背包中以此类推，直到确定第一个物品是否被装入背包为止。逆推代码如下： //逆推求装入的物品 j=m; for(i=row-1;i>0;i--) { if(value[i][j]>value[i-1][j]) { c[i]=1; j-=w[i]; } } 4. 代码如下动态规划与回溯法解决0-1背包问题
算法设计实验_贪心算法背包问题
01背包问题动态规划详解
背包问题(贪心算法)
动态规划之01背包问题(最易理解的讲解)
背包问题贪心法
解0-1背包问题的动态规划算法
用贪心法求解0-1背包问题
01背包问题动态规划详解及C++代码
算法分析与程序设计动态规划及回溯法解背包问题
背包问题-贪心法和动态规划法求解
0-1背包问题动态规划详解及代码
动态规划法解0-1背包问题举例
c应用贪心算法求解背包问题
用蛮力法、动态规划法和贪心法求解01背包问题
0-1背包问题动态规划详解及代码
动态规划算法-01背包问题
动态规划之-0-1背包问题及改进
01背包问题(动态规划法)
相关文档
- 0-1背包问题动态规划
- 动态规划之01背包问题(最易理解的讲解)
- (完整版)01背包问题
- 0-1背包问题用动态规划的递归实现与非递归实现
- 0-1背包问题-贪心法和动态规划法求解1
- 动态规划之 0-1背包问题及改进
- 01背包问题动态规划详解及C++代码
- 01背包问题动态规划详解及c代码
- 0-1背包问题动态规划详解及代码
- 动态规划01背包问题
- 01背包问题动态规划详解
- 动态规划之-0-1背包问题及改进
- 01背包问题动态规划 Python
- 动态规划之01背包问题及改进
- 动态规划详解01背包问题knapsack
- 算法分析与程序设计动态规划及回溯法解背包问题
- 动态规划法解0-1背包问题举例
- 0-1背包问题之动态规划法 -
- 解01背包问题的动态规划算法
- 动态规划算法01背包问题PPT