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

问题描写：

在部份背包问题中，可以无须拿走整个一件物品，而是可以拿走该物品的任意部份。以此求得在限定背包总重量，从给定的物品中进行选择的情况下的最好（总价值最高）的选择方案。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5741.html

细节须知：文章源自微观生活（93wg.com）微观生活-https://93wg.com/5741.html

分别输出到同文件夹下两个文文章源自微观生活（93wg.com）微观生活-https://93wg.com/5741.html

算法原理：文章源自微观生活（93wg.com）微观生活-https://93wg.com/5741.html

先求出所有物品的单位重量价值并进行由大到小的排序。其次从排序处于首位的物品开始选择直到没法完全装入背包的物品，将其部份装入背包以填满背包的总重量，从而求得价值最高的选择方案。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5741.html

程序设计思路：文章源自微观生活（93wg.com）微观生活-https://93wg.com/5741.html

① 数据结构：结构体中存储物品序号、物品的重量、物品的价值、物品的单位重量价值；文章源自微观生活（93wg.com）微观生活-https://93wg.com/5741.html

② 应用C++自带的sort函数对结构体依照物品的单位重量价值进行降序排列；文章源自微观生活（93wg.com）微观生活-https://93wg.com/5741.html

③ 从排序处于首位的物品开始选择直到没法完全装入背包的物品，将其部份装入背包以填满背包的总重量，从而求得价值最高的选择方案。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5741.html

时间繁杂性分析：文章源自微观生活（93wg.com）微观生活-https://93wg.com/5741.html

首先，需要对输入的物品单位重量价值进行非减序排序，需要用O（nlogn）的时间。其次，当输入的物品已按物品单位重量价值非减序排列，算法只需θ（n）的时间选择n个物品，使算法可以求得价值最高的选择方案。

生成的数据可导入EXCEL中进行数据分析生成份析图表。

博客园：Weisswire

想要在程序员生涯内有更高的成绩的话，C/C++就是一个既可以强化思惟能力，又可以打好编程基础的编程语言，你想要做软件开发，成为核心程序员的话，学习C/C++的话笔者有一个C/C++的编程千人羣（Q艘索：C语言编程学习会萃地（无言树立））你如果感觉自学C/C++语言有难题的话，有兴致学习或者了解一下C/C++编程的小火伴就能够进来交换。

以上就是微观生活（93wg.com）关于“C++编程笔记：贪心算法实现部份背包问题”的详细内容，希望对大家有所帮助！