贪心算法实验(求解背包问题)

背包问题的算法研究及应用背包问题是一种经典的组合优化问题，常常被用来研究在有限的空间下如何使价值最大化。

背包问题可以分为 01 背包问题、完全背包问题、多重背包问题和混合背包问题等多种类型。

这些问题的求解方法也各有特点，需要根据具体问题进行选择。

本文主要介绍 01 背包问题和完全背包问题的求解算法及应用。

一、01 背包问题01 背包问题指的是在一个容量为 V 的背包中装入物品，每件物品都有自己的体积 vi 和价值 wi，问怎样装能使背包价值最大化，且物品不能重复使用。

01 背包问题可以用贪心算法或动态规划算法进行求解。

贪心算法的思想是每次选择当前最优的物品，直到背包无法继续装下为止。

但是贪心算法不能保证一定能获得最优解。

动态规划算法则是将问题分解为子问题，并通过递推关系式来求解。

具体来说，我们定义一个 dp[i][j] 表示将前 i 件物品放入容量为 j 的背包中所能获得的最大价值，则有：dp[i][j] = max(dp[i-1][j], dp[i-1][j-vi]+wi)其中 max 表示取两者中的最大值，dp[i-1][j] 表示不选择第 i 件物品，dp[i-1][j-vi]+wi 表示选择第 i 件物品放入背包中。

根据递推关系式，我们可以得到目标值为dp[n][V]，其中 n 表示物品个数。

二、完全背包问题完全背包问题指的是在一个容量为 V 的背包中装入物品，每件物品都有自己的体积 vi 和价值 wi，问怎样装能使背包价值最大化，且每件物品可以无限使用。

完全背包问题和 01 背包问题类似，也可以用贪心算法或动态规划算法进行求解。

贪心算法的思想是每次选择当前最优的物品，并一直选择直到不能再在背包中装入为止。

但是贪心算法仍然不能保证获得最优解。

动态规划算法则是将问题分解为子问题，并通过递推关系式来求解。

与 01 背包问题相比，完全背包问题的递推关系式与之略有不同，具体来说，我们定义一个 dp[i][j] 表示将前 i 件物品放入容量为 j 的背包中所能获得的最大价值，则有：dp[i][j] = max(dp[i-1][j-k*vi]+k*wi)其中 max 表示取两者中的最大值，k 表示第 i 件物品中的物品数量。

第1篇一、实验目的通过本次实验，掌握常见算法的设计原理、实现方法以及性能分析。

通过实际编程，加深对算法的理解，提高编程能力，并学会运用算法解决实际问题。

二、实验内容本次实验选择了以下常见算法进行设计和实现：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。

2. 查找算法：顺序查找、二分查找。

3. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）。

4. 动态规划算法：0-1背包问题。

三、实验原理1. 排序算法：排序算法的主要目的是将一组数据按照一定的顺序排列。

常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。

2. 查找算法：查找算法用于在数据集中查找特定的元素。

常见的查找算法包括顺序查找和二分查找。

3. 图算法：图算法用于处理图结构的数据。

常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）等。

4. 动态规划算法：动态规划算法是一种将复杂问题分解为子问题，通过求解子问题来求解原问题的算法。

常见的动态规划算法包括0-1背包问题。

四、实验过程1. 排序算法（1）冒泡排序：通过比较相邻元素，如果顺序错误则交换，重复此过程，直到没有需要交换的元素。

（2）选择排序：每次从剩余元素中选取最小（或最大）的元素，放到已排序序列的末尾。

（3）插入排序：将未排序的数据插入到已排序序列中适当的位置。

（4）快速排序：选择一个枢纽元素，将序列分为两部分，使左侧不大于枢纽，右侧不小于枢纽，然后递归地对两部分进行快速排序。

（5）归并排序：将序列分为两半，分别对两半进行归并排序，然后将排序好的两半合并。

（6）堆排序：将序列构建成最大堆，然后重复取出堆顶元素，并调整剩余元素，使剩余元素仍满足最大堆的性质。

2. 查找算法（1）顺序查找：从序列的第一个元素开始，依次比较，直到找到目标元素或遍历完整个序列。

第1篇一、实验目的本次实验旨在通过实际操作，加深对算法设计方法、基本思想、基本步骤和基本方法的理解与掌握。

通过具体问题的解决，提高利用课堂所学知识解决实际问题的能力，并培养综合应用所学知识解决复杂问题的能力。

二、实验内容1. 实验一：排序算法分析- 实验内容：分析比较冒泡排序、选择排序、插入排序、快速排序、归并排序等基本排序算法的效率。

- 实验步骤：1. 编写各排序算法的C++实现。

2. 使用随机生成的不同规模的数据集进行测试。

3. 记录并比较各算法的运行时间。

4. 分析不同排序算法的时间复杂度和空间复杂度。

2. 实验二：背包问题- 实验内容：使用贪心算法、回溯法、分支限界法解决0-1背包问题。

- 实验步骤：1. 编写贪心算法、回溯法和分支限界法的C++实现。

2. 使用标准测试数据集进行测试。

3. 对比分析三种算法的执行时间和求解质量。

3. 实验三：矩阵链乘问题- 实验内容：使用动态规划算法解决矩阵链乘问题。

- 实验步骤：1. 编写动态规划算法的C++实现。

2. 使用不同规模的矩阵链乘实例进行测试。

3. 分析算法的时间复杂度和空间复杂度。

4. 实验四：旅行商问题- 实验内容：使用遗传算法解决旅行商问题。

- 实验步骤：1. 设计遗传算法的参数，如种群大小、交叉率、变异率等。

2. 编写遗传算法的C++实现。

3. 使用标准测试数据集进行测试。

4. 分析算法的收敛速度和求解质量。

三、实验结果与分析1. 排序算法分析- 通过实验，我们验证了快速排序在平均情况下具有最佳的性能，其时间复杂度为O(nlogn)，优于其他排序算法。

- 冒泡排序、选择排序和插入排序在数据规模较大时效率较低，不适合实际应用。

2. 背包问题- 贪心算法虽然简单，但在某些情况下无法得到最优解。

- 回溯法能够找到最优解，但计算量较大，时间复杂度较高。

- 分支限界法结合了贪心算法和回溯法的特点，能够在保证解质量的同时，降低计算量。

3. 矩阵链乘问题- 动态规划算法能够有效解决矩阵链乘问题，时间复杂度为O(n^3)，空间复杂度为O(n^2)。

贪心算法及几个常用的例题贪心算法：一、基本概念：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。

必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

二、贪心算法的基本思路：1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

三、贪心算法适用的问题贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

实际上，贪心算法适用的情况很少。

一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

四、贪心算法的实现框架从问题的某一初始解出发；while （能朝给定总目标前进一步）利用可行的决策，求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；五、贪心策略的选择因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。

几个经典的例子：一、定义什么是贪心算法呢？所谓贪心算法是指，在对问题求解时，总是做出在当前看来最好的选择。

也就是说，不从整体最优解出发来考虑，它所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题都能产生整体最优解或整体最优解的近似解。

贪心算法的基本思路如下：1. .建立数学模型来描述问题。

2. 把求解的问题分成若干个子问题。

3. 对每个子问题求解，得到每个子问题的局部最优解。

4. 把每个子问题的局部最优解合成为原来问题的一个解。

01背包问题：1.递归思想0- 1 背包问题如果采用递归算法来描述则非常清楚明白, 它的算法根本思想是假设用布尔函数knap( s, n) 表示n 件物品放入可容质量为s 的背包中是否有解( 当knap 函数的值为真时说明问题有解,其值为假时无解) . 我们可以通过输入s 和n 的值, 根据它们的值可分为以下几种情况讨论:( 1) 当s= 0时可知问题有解, 即函数knap( s, n) 的值为true; ( 2) 当s< 0 时这时不可能,所以函数值为false; ( 3) 当输入的s> 0 且n< 1 时即总物品的件数不足1, 这时函数值为false,只有s> 0 且n \1 时才符合实际情况,这时又分为两种情况: ( 1) 选择的一组物体中不包括Wn则knap( s, n) 的解就是knap( s, n- 1) 的解. ( 2) 选择的一组物体中包括Wn 则knap( s, n) 的解就是knap( s- Wn, n- 1) 的解. 这样一组Wn 的值就是问题的最佳解. 这样就将规模为n 的问题转化为规模为n- 1 的问题. 综上所述0- 1 背包问题的递归函数定义为:knap( s, n) =∕true, s= 0︳false, s< 0︳false, s> 0 且n< 1\knap( s, n- 1) 或knap( s- Wn, n- 1) , s> 0 且n>= 1采用此法求解0- 1 背包问题的时间复杂度为O( n) . 上述算法对于所有物品中的某几件恰能装满背包时能准确求出最佳解. 但一般情况是对于某一些物品无论怎么装都不能装满背包, 必须要按背包的最大容量来装. 如物品件数为4, 其质量分别为: 10, 2, 5, 4, 背包的容量为20, 则这四件物品无论怎么放都不能恰好装满背包, 但应能最大限度装, 即必须装下10, 5, 4 这三件物品, 这样就能得到最大质量19. 对于这种装不满的背包它的解决办法是这样的: 按所有物品的组合质量最大的方法装背包, 如果还装不满,则我们可以考虑剩余空间能否装下所有物品中最小的那件, 如果连最小的都装不下了则说明这样得到的解是最佳解, 问题解决. 这样我们必须先找出所有n 件物品中质量最小的那件( 它的质量为Min) , 但是为了问题的解决我们不能增加运算次数太多, 并且必须运用上述递归函数. 那么我们可通过修改s 的值即背包的容量, 从背包容量s 中减去k( 它的值是从0 到Min- 1 之间的一个整数值) , 再调用递归函数. 当k= 0 时即能装满背包, 其它值也能保证背包能最大限度装满, 这样所有问题都解决了.①例题一：简单背包问题Time Limit: 1000MS Memory Limit: 65535KBSubmissions: 2217 Accepted: 408Description设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。

多背包问题近似解法及其近似⽐多背包问题：给定n个物品，其中物品i的价格是vi,重量是wi,有m个背包，背包j最⼤能装物品重量为Bj,求这些背包能够装下物品的最⾼价格，其中每个物品要么完全放⼊背包要么不放⼊。

(1),给出⼀个求解该问题的近似算法。

(2),设所有Bj都相等，分析你给出的算法的近似⽐。

这个问题到底有没有⾮近似的⽅法？这个是不是NP问题呢？虽然有些疑惑，但还是找出⼀个近似算法吧！(1),这⾥⽤贪⼼算法，依次从剩余的物品中⽤贪⼼算法使得第i个背包中的物品价值达到最⼤，i从1到m。

(2),这⾥我们可以证明这个近似算法具有常近似⽐。

设最优解的总价值为C*,我们要证明C*/C为常数, C为这个近似解的最⼤价值。

如果有背包没有物品的话，C*=C。

这⾥我们假设每个背包⾥都有物品。

　假设物品可以部分放⼊背包，那么我们可以⽤⼀个贪⼼算法解决上⾯的优化问题，得到的解的最⼤价值为C', 每个背包j的容量为Wj'=B，价值为Vj'，那么C'>=C*。

⽅案(1)中，假设每个背包j的容量为Wj,所含物品价值为Vj，那么Vj/Wj >= Vj'/Wj'。

在⽅案（1）基础上，我们⽤单位价值为Vj/Wj的物品把背包j填满，最后物品的总价值为C'', 每个背包j的所含物品的重量为Wj''=B, Vj'', 那么Vj''/Wj'' = Vj/Wj >= Vj'/Wj'，所以C'' >= C'。

⼜有C'' <= kC，其中，k = B/min{wi}。

所以C* <= C' <= C'' <= kC, => C*/C <=k(常数)。

得证。

这⾥有⼀个更优的解法，近似⽐为2.。

（0-1）背包问题的解法小结1．动态规划法递推关系：– 考虑一个由前i 个物品(1≤i ≤n )定义的实例，物品的重量分别为w 1,…,w i ，价值分别为v 1，…，v i ，背包的承重量为j (1≤j ≤W )。

设V [I,j]为该实例的最优解的物品总价值– 分成两类子集：• 根据定义，在不包括第i 个物品的子集中，最优子集的价值是V [i -1,j ]• 在包括第i 个物品的子集中(因此，j －w ≥0)，最优子集是由该物品和前i -1个物品中能够放进承重量为i －w j 的背包的最优子集组成。

这种最忧子集的总价值等于v i +V [i -1,j -w i ].0]0,[时，0 当0;][0,时，0初始条件：当],1[}],1[],,1[max{],[=≥=≥<≥⎩⎨⎧-+---=i V i j V j w j w j j i V v w j i V j i V j i V i i i i以记忆功能为基础的算法：用自顶向下的方式对给定的问题求解，另外维护一个类似自底向上动态规划算法使用的表格。

一开始的时候，用一种“null”符号创始化表中所有的单元，用来表明它们还没有被计算过。

然后，一旦需要计算一个新的值，该方法先检查表中相应的单元：如果该单元不是“null ”，它就简单地从表中取值；否则，就使用递归调用进行计算，然后把返回的结果记录在表中。

算法 MFKnapsack(I,j)//对背包问题实现记忆功能方法//输入：一个非负整数i 指出先考虑的物品数量，一个非负整数j 指出了背包的承重量 //输出：前i 个物品的最伏可行子集的价值//注意：我们把输入数组Weights[1..n],Values[1..n]和表格V[0..n,0..W]作为全局变量，除了行0和列0用0初始化以外，V 的所有单元都用-1做初始化。

if V[I,j]<01if j<Weights[i]value ←MFKnapsack(i-1,j)elsevalue ←max(MFKnapsack(i-1),j), Value[i]+MFKnapsack(i-1,j-eights[i]))V[I,j]←valuereturn V[I,j]2．贪心算法1) 背包问题基本步骤：首先计算每种物品单位重量的价值Vi/Wi ，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。

算法背包问题实验题目：背包问题实验目的：掌握动态规划、贪心算法的原理，并能够按其原理编程实现解决背包问题，以加深对上述方法的理解。

实验内容：一个旅行者准备随身携带一个背包. 可以放入背包的物品有n 种, 每种物品的重量和价值分别为 wj , vj . 如果背包的最大重量限制是 b, 怎样选择放入背包的物品以使得背包 的价值最大? 目标函数： 约束条件： 线性规划问题由线性条件约束的线性函数取最大或最小的问题整数规划问题 线性规划问题的变量 xj 都是非负整数Fk(y)：装前 k 种物品, 总重不超过 y, 背包的最大价值i(k,y)：装前 k 种物品, 总重不超过 y, 背包达最大价值时装入物品的最大标号 递推方程、边界条件、标记函数实例计算：v1 = 1, v2 = 3, v3 = 5, v4 = 9, w1 = 2, w2 = 3, w3 = 4, w4 = 7, b = 10Fk(y) 的计算表如下: K/y 1 2 3 4 5 6 7 8 9 10 1 0 1 1 2 2 3 3 4 4 5 2 0 1 3 3 4 6 6 7 9 9 3 0 1 3 5 5 6 8 10 10 11 4135569101012实验步骤： 1、分析题目；2、打开NetBeans 软件，新建一个名叫 Knapsackdxj 的项目，并对其进行保存；N,max 11∈≤∑∑==j nj j jnj jj x b x wx v)()(0,0)0(,0,0)(})(),(max{)(11101<-∞=⎥⎦⎥⎢⎣⎢=≤≤=≤≤=+-=-y y F v w y y F nk F b y y F v w y F y F y F k k k k k k k3在新建的项目下对我们所分析的题目进行编写；4、调试所编写的程序；5、运行文件，并对其进行测试，看是否正确。

实验结果：实验小结：在做本次实验之前，自己对动态规划、贪心算法的原理不是非常的理解，花了很多时间看了课本上的相关内容。