問題描述：
在部分背包問題中，可以不必拿走整個一件物品，而是可以拿走該物品的任意部分。以此求得在限定背包總重量，從給定的物品中進行選擇的情況下的最佳（總價值最高）的選擇方案。
細節(jié)須知：
分別輸出到同文件夾下兩個文本文件中，名稱分別是：“backpack-object.txt”和“backpack-weight.txt”。
算法原理：
先求出所有物品的單位重量價值并進行由大到小的排序。其次從排序處于首位的物品開始選擇直到無法完整裝入背包的物品，將其部分裝入背包以填滿背包的總重量，從而求得價值最高的選擇方案。
程序設(shè)計思路：
① 數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)體中存儲物品序號、物品的重量、物品的價值、物品的單位重量價值；
② 利用C++自帶的sort函數(shù)對結(jié)構(gòu)體按照物品的單位重量價值進行降序排列；
③ 從排序處于首位的物品開始選擇直到無法完整裝入背包的物品，將其部分裝入背包以填滿背包的總重量，從而求得價值最高的選擇方案。
時間復(fù)雜性分析：
首先，需要對輸入的物品單位重量價值進行非減序排序，需要用O（nlogn）的時間。其次，當(dāng)輸入的物品已按物品單位重量價值非減序排列，算法只需θ（n）的時間選擇n個物品，使算法可以求得價值最高的選擇方案。
生成的數(shù)據(jù)可導(dǎo)入EXCEL中進行數(shù)據(jù)分析生成分析圖表。
博客園：Weisswire
1.《c語言背包問題 C++編程筆記：貪心算法實現(xiàn)部分背包問題》援引自互聯(lián)網(wǎng)，旨在傳遞更多網(wǎng)絡(luò)信息知識，僅代表作者本人觀點，與本網(wǎng)站無關(guān)，侵刪請聯(lián)系頁腳下方聯(lián)系方式。
2.《c語言背包問題 C++編程筆記：貪心算法實現(xiàn)部分背包問題》僅供讀者參考，本網(wǎng)站未對該內(nèi)容進行證實，對其原創(chuàng)性、真實性、完整性、及時性不作任何保證。
3.文章轉(zhuǎn)載時請保留本站內(nèi)容來源地址，http://f99ss.com/keji/347311.html