01背包问题的c++实现共4资料

1、01背包问题的C+实现Abstract: the 0 / 1 knapsack problem of computer science is aClassiC problem. In praCtiCal problems, we often need to solve the optimization problem, the study of how to limited Conditions, find the optimal value of optimization funCtion .Greedy algorithm to solve suCh problems is an intu

2、itive method. BeCause the attempt to find the optimal solution Can be Completed by Choosing through a series of loCal optimization, or Conversely, an optimal solution Contains optimal solutions of its subproblems. Therefore, the optimal substruCtural with the nature of these problems Can be greedy a

3、lgorithm. The main idea is: the optimal solution by the stepwise method of ConstruCtion at eaCh stage in the solution proCess, what are looking for an optimal deCision. DeCision onCe made, it Can not be Changed.1、背包问题及贪婪准则0/1背包问题是计算机算法中一个NP完全难题。背包问题是贪婪算法的典型应用。在背包问题中，需对容量为的背包进行装载。从个物品中选 取装入背包的物品，每件物品

4、的重量为，价值为。对于可行的背包装载， 背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价 值最高，即取得最大值。约束条件为和在这个表达式中，需求出的值。表 示物品装入背包中，表示物品不装入背包 1,2 。在求解中我们需要考虑贪婪策略：本例中贪婪准则是按价值密度递减构造贪婪算法，这种选择准则为：从剩余物品中选择可装入包的值最大的 物品，这种策略也不能保证得到最优解。2、背包问题的实际问题实际问题：在 0/1 背包问题中，需对容量为 c 的背包进行装载。从 n 个物品中选取装入背包的物品，每件物品 i 的重量为 wi ，价值为 pi 。对 于可行的背包装载，背包中物品的总重量不能超

5、过背包的容量，最佳装载 是指所装入的物品价值最高，即取得最大值。约束条件为和(1 < i < n)。对重量为的“背包”进行装载。从个物品中选择需要装入“背包”的 物品，每件物品的重量为，价值为，例如： 。使得在满足取得最大值，其 中约束条件为和3、背包问题算法分析及数据结构3.1 算法分析按照价值密度递减的贪婪准则，第一次取的最大的一个，放入“背 包”，之后在满足不大于重量的条件下，依次取剩余物品中价值密度最大的，逐个放入。最后计算所放物品价值的总和。3.2 数据结构对于任意物品个数和“背包”重量限制，输入 b 。通过构建函数 voidgreedy(double v,double

6、w,int c,int n)，创建长度为且全部初始化为 0 的四个数组。接收对应的价值密度，即，并对数组中的元素从大到小排序和对应的下标赋给数组和。对下标值对应的重量相加得到满足重量限制的放入的物品。并求得相对应的价值 . 输入选取的物品和即为所求4、运行结果分析及说明输入，得到结果如下：4.1 求解过程分析 对应，价值密度为，按照价值密度递减的贪婪准则，首先选定物品2，此时。其次选择物品 1，此时再选择物品 5，此时若接着选择物品 4，则故此时不再选择物品，求解结束。 最终结果为，即为此贪婪准则下的所求的解。4.2 贪婪算法求解背包问题的说明 以上所求的结果不是最优解，例如取则此时。 故贪婪算法不能保证得到最优解，这是因为 0/1 背包问题是一个 NP- 复杂问题，也许根本就不可能找到具有多项式时间的算法。虽然按非递 （增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的 解 3 。它是一个好的启发式算法，且大多数时候能很好地接近最优算法。 故需要通过改进不同的贪婪准则可以逐步接近最优的结果。但贪婪算法还 是在此类问题的求解中发挥着很大的作用，是我们求解复杂最优化问题的 常用的方法。希望以上资料对你有