问题描述:
在部分背包问题中,可以不必拿走整个一件物品,而是可以拿走该物品的任意部分。以此求得在限定背包总重量,从给定的物品中进行选择的情况下的最佳(总价值最高)的选择方案。
细节须知:
分别输出到同文件夹下两个文本文件中,名称分别是:“backpack-object.txt”和“backpack-weight.txt”。
算法原理:
先求出所有物品的单位重量价值并进行由大到小的排序。其次从排序处于首位的物品开始选择直到无法完整装入背包的物品,将其部分装入背包以填满背包的总重量,从而求得价值最高的选择方案。
程序设计思路:
① 数据结构:结构体中存储物品序号、物品的重量、物品的价值、物品的单位重量价值;
② 利用C++自带的sort函数对结构体按照物品的单位重量价值进行降序排列;
③ 从排序处于首位的物品开始选择直到无法完整装入背包的物品,将其部分装入背包以填满背包的总重量,从而求得价值最高的选择方案。
时间复杂性分析:
首先,需要对输入的物品单位重量价值进行非减序排序,需要用O(nlogn)的时间。其次,当输入的物品已按物品单位重量价值非减序排列,算法只需θ(n)的时间选择n个物品,使算法可以求得价值最高的选择方案。
生成的数据可导入Excel中进行数据分析生成分析图表。
博客园:Weisswire
想要在程序员生涯内有更高的成就的话,C/C++就是一个既可以强化思维能力,又可以打好编程基础的编程语言,你想要做软件开发,成为核心程序员的话,学习C/C++的话笔者有一个C/C++的编程千人羣(Q艘索:C语言编程学习聚集地(无言建立))你如果感觉自学C/C++语言有困难的话,有兴趣学习或者了解一下C/C++编程的小伙伴就可以进来交流。