求得价值最高的选择方案(时间复杂性分析)(图)

问题描述：

在部分背包问题中，您可以拿取物品的任何部分，而不是拿走整个物品。这样，在限制背包总重量的情况下，从给定的物品中进行选择，就得到了最佳（总价值最高）的选择方案。

细节：

它们被输出到同一文件夹中的两个文本文件贪心算法 背包问题 c，名称分别为：“backpack-object.txt”和“backpack-weight.txt”。

算法原理：

先找出所有物品的单位重量值，从大到小排序。其次，从排名靠前的物品开始，直到无法完全装入背包的物品，部分装入背包，填满背包的总重量，从而获得价值最高的选项.

程序设计思路：

数据结构：结构中存储了物品的序号、物品的重量、物品的价值、物品的单位重量值；

使用C++自带的排序功能，将结构按照物品的单位重量值降序排列；

从排名靠前的物品开始，直到无法完全装入背包的物品贪心算法 背包问题 c，部分装入背包以填满背包的总重量，找到价值最高的选项。

时间复杂度分析：

首先，需要对输入项的单位权重值进行非降序排序，耗时O(nlogn)。其次，当输入的项目按照项目的单位权重值以非递减的顺序排列时，算法只需要 θ(n) 时间来选择 n 个项目，这样算法就可以找到价值最高的选项。

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

博客园：Weisswire