問題描述：

在部分背包問題中，可以不必拿走整個一件物品，而是可以拿走該物品的任意部分。以此求得在限定背包總重量，從給定的物品中進行選擇的情況下的最佳（總價值最高）的選擇方案。

細節須知：

分別輸出到同文件夾下兩個文本文件中，名稱分別是：“backpack-object.txt”和“backpack-weight.txt”。

算法原理：

先求出所有物品的單位重量價值并進行由大到小的排序。其次從排序處于首位的物品開始選擇直到無法完整裝入背包的物品，將其部分裝入背包以填滿背包的總重量，從而求得價值最高的選擇方案。

程序設計思路：

① 數據結構：結構體中存儲物品序號、物品的重量、物品的價值、物品的單位重量價值；

② 利用C++自帶的sort函數對結構體按照物品的單位重量價值進行降序排列；

③ 從排序處于首位的物品開始選擇直到無法完整裝入背包的物品，將其部分裝入背包以填滿背包的總重量，從而求得價值最高的選擇方案。

時間復雜性分析：

首先，需要對輸入的物品單位重量價值進行非減序排序，需要用O（nlogn）的時間。其次，當輸入的物品已按物品單位重量價值非減序排列，算法只需θ（n）的時間選擇n個物品，使算法可以求得價值最高的選擇方案。

生成的數據可導入EXCEL中進行數據分析生成分析圖表。

博客園：Weisswire

學習C/C++編程可以湫湫掃下方二維碼，學習編程，碼上開始！

?

總結

以上是生活随笔為你收集整理的C++编程笔记：贪心算法实现部分背包问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。