江苏龙网

  1. 主页 > 生活百科 > >

C++编程笔记：贪心算法实现部分背包问题

C++


C++编程笔记：贪心算法实现部分背包问题

文章插图
 
问题描述：
在部分背包问题中，可以不必拿走整个一件物品，而是可以拿走该物品的任意部分 。以此求得在限定背包总重量，从给定的物品中进行选择的情况下的最佳（总价值最高）的选择方案 。
细节须知：
分别输出到同文件夹下两个文本文件中，名称分别是：“backpack-object.txt”和“backpack-weight.txt” 。
算法原理：
【C++编程笔记：贪心算法实现部分背包问题】先求出所有物品的单位重量价值并进行由大到小的排序 。其次从排序处于首位的物品开始选择直到无法完整装入背包的物品，将其部分装入背包以填满背包的总重量，从而求得价值最高的选择方案 。
C++编程笔记：贪心算法实现部分背包问题

文章插图
 
 
C++编程笔记：贪心算法实现部分背包问题

文章插图
 
 
C++编程笔记：贪心算法实现部分背包问题

文章插图
 
程序设计思路：
① 数据结构：结构体中存储物品序号、物品的重量、物品的价值、物品的单位重量价值；
② 利用C++自带的sort函数对结构体按照物品的单位重量价值进行降序排列；
③ 从排序处于首位的物品开始选择直到无法完整装入背包的物品，将其部分装入背包以填满背包的总重量，从而求得价值最高的选择方案 。
时间复杂性分析：
首先，需要对输入的物品单位重量价值进行非减序排序，需要用


    推荐阅读


    上一篇：肯德基豆腐花 肯德基豆豆乳撞豆花好喝吗

    下一篇：钱承鸿,台湾茶界挺进大陆市场是大势