問題說明
有N件物品和一個容量為V的背包。
第i件物品的重量是w[i],價值是v[i]。
求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量,
且價值總和最大。
功能說明
本程序用動態規劃的思想解決了背包問題,并用了兩種算法:迭代法、遞歸法。在迭代法中實現了打印背包問題的表格。
代碼簡述
通過用戶輸入數據,程序輸入檢測,動態分配空間,選擇算法, 用動態規劃的思想求解背包問題。
迭代法:
通過遍歷n行W列,迭代每行每列的值,并把最優解放到 n行(在數組中為第n+1行)W列(在數組中為第W+1列)中。
遞歸法:
通過每次返回前i個物品和承重為j的最優解, 遞歸計算總背包問題的最優解。
源碼示例
using namespace std;int **T = NULL; // 存儲背包問題表格的數組指針// 返回兩個值的最大值int max(int a, int b) {return (a > b) ? a : b;}// 迭代法,能顯示背包問題的表格int packIterative(int n, int W, int *w, int *v) {// 循環遍歷n行for (int i = 1; i <= n; ++i){// 循環遍歷W列for (int j = 1; j <= W; ++j){//第i個物品能裝下,則比較包括第i個物品和不包括第i個物品,取其最大值if (w[i] <= j)T[i][j] = max(v[i] + T[i - 1][j - w[i]], T[i - 1][j]);// 第i個物品不能裝下,則遞歸裝i-1個elseT[i][j] = T[i - 1][j];}}return T[n][W];}// 遞歸法,不支持顯示背包問題的表格int packRecursive(int n, int W, int *w, int *v) {// 結束條件(初始條件),i或者j為0時最大總價值為0if (n == 0 || W == 0) {return 0;}// 第i個物品不能裝下,則遞歸裝i-1個if (w[n] > W) {return packRecursive(n - 1, W, w, v);}//第i個物品能裝下,則比較包括第i個物品和不包括第i個物品,取其最大值else {return max(v[n] + packRecursive(n - 1, W - w[n], w, v), packRecursive(n - 1, W, w, v));}}// 打印背包問題的表格void printT(int n, int W){// 打印n行for (auto i = 0; i <= n; i++){// 打印行數cout << i << ": ";// 打印W列for (int w = 0; w <= W; w++){cout << T[i][w] << " ";}// 換行cout << endl;}}int main() {int *w = NULL; // 存儲每件物品重量的數組指針int *v = NULL; // 存儲每件物品價值的數組指針int n; // 物品個數nint W; // 背包總承重Wcout << "---------------- 背包問題 ----------------" << endl;cout << "請輸入物品數 n (n>=0) " << endl;// 輸入背包數cin >> n;if (cin.fail() || n < 0){cout << "輸入n錯誤!" << endl;system("pause");return 0;}cout << "請輸入背包承重量 W (W>=0) " << endl;// 輸入背包承重量cin >> W;if (cin.fail() || W < 0){cout << "輸入W錯誤!" << endl;system("pause");return 0;}// 分配空間// 對w和v分配n+1大小w = new int[n + 1];v = new int[n + 1];// 對T分配n+1行,并初始化為0T = new int *[n + 1]();// 對T分配W+1列,并初始化為0for (auto i = 0; i <= n; i++){T[i] = new int[W + 1]();}// 輸入背包的重量和價值for (auto i = 1; i <= n; i++){cout << "請輸入第 " << i << " 個物品的重量和價值(用空格隔開)" << endl;cin >> w[i] >> v[i];if (cin.fail() || w[i] < 0 || v[i] < 0){cout << "輸入錯誤!" << endl;system("pause");return 0;}}cout << "------------------------------------------------" << endl;cout << "請選擇算法:" << endl;cout << "【1】迭代法" << endl;cout << "【2】遞歸法" << endl;cout << "------------------------------------------------" << endl;int choose;// 輸入算法的選擇cin >> choose;switch (choose){case 1:{// 迭代法,能顯示背包問題的表格cout << "能裝下物品的最大價值為 " << packIterative(n, W, w, v) << endl;cout << "------------------------------------------------" << endl;printT(n, W);break;}case 2:{// 遞歸法,不支持顯示背包問題的表格cout << "能裝下物品的最大價值為 " << packRecursive(n, W, w, v) << endl;break;}default:{cout << "輸入錯誤!" << endl;break;}}cout << "------------------------------------------------" << endl;delete w;delete v;for (int i = 0; i <= n; ++i) {delete[] T[i];}delete[] T;system("pause");return 0;}
今天的分享就到這里了,大家要好好學C++喲~
聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。
舉報投訴
-
數據
+關注
關注
8文章
7335瀏覽量
94765 -
C++
+關注
關注
22文章
2124瀏覽量
77112
原文標題:C++經典算法問題:背包問題(迭代+遞歸算法)!含源碼示例
文章出處:【微信號:cyuyanxuexi,微信公眾號:C語言編程學習基地】歡迎添加關注!文章轉載請注明出處。
發布評論請先 登錄
相關推薦
熱點推薦
CW32系列MCU在Eclipse GCC + JLink下的使用示例分享
CW32系列MCU在Eclipse GCC + JLink下的使用示例:
1、下載安裝Eclipse IDE for Embedded C/C++ Developers。
2、下載安裝
發表于 02-02 06:57
keil實現c與c++混合編程
起因項目中使用到一個開源的模擬IIC的庫,封裝的比較好,但是是使用c++寫的。于是將其移植到自己的項目中,主要有以下三步操作:
在工程選項中 C/C++中去掉勾選
發表于 01-26 08:58
C語言與C++的區別及聯系
缺點:性能比面向過程低。
二、具體語言上的區別
1、關鍵字的不同
C語言有32個關鍵字;C++有63個關鍵字。
2、后綴名不同
C源文件后綴.c,
發表于 12-24 07:23
C語言和C++之間的區別是什么
區別
1、面向對象編程 (OOP):
C語言是一種面向過程的語言,它強調的是通過函數將任務分解為一系列步驟進行執行。
C++在C語言的基礎上擴展了面向對象的特性,支持類(class)、封裝、繼承
發表于 12-11 06:23
C/C++條件編譯
條件編譯是一種在編譯時根據條件選擇性地包含或排除部分代碼的處理方法。在 C/C++ 中,條件編譯使用預處理指令 #ifdef、#endif、#else 和 #elif 來實現。常用的條件編譯指令有
發表于 12-05 06:21
C++程序異常的處理機制
1、什么是異常處理?
有經驗的朋友應該知道,在正常的C和C++編程過程中難免會碰到程序不按照原本設計運行的情況。
最常見的有除法分母為零,數組越界,內存分配失效、打開相應文件失敗等等。
一個程序
發表于 12-02 07:12
C/C++代碼靜態測試工具Perforce QAC 2025.3的新特性
?Perforce Validate?中?QAC?項目的相對/根路徑的支持。C++?分析也得到了增強,增加了用于檢測 C++?并發問題的新檢查,并改進了實體名稱和實
技能+1!如何在樹莓派上使用C++控制GPIO?
和PiGPIO等庫,C++可用于編程控制樹莓派的GPIO引腳。它提供了更好的性能和控制能力,非常適合對速度和精度要求較高的硬件項目。在樹莓派社區中,關于“Python
C++ 與 Python:樹莓派上哪種語言更優?
Python是樹莓派上的首選編程語言,我們的大部分教程都使用它。然而,C++在物聯網項目中同樣廣受歡迎且功能強大。那么,在樹莓派項目中選擇哪種語言更合適呢?Python因其簡潔性、豐富的庫和資源而被
在OpenVINO? C++代碼中啟用 AddressSanitizer 時的內存泄漏怎么解決?
在 OpenVINO? C++代碼中啟用 AddressSanitizer 時遇到內存泄漏:
\"#0 0xaaaab8558370 in operator new(unsigned
發表于 06-23 07:16
主流的 MCU 開發語言為什么是 C 而不是 C++?
在單片機的地界兒里,C語言穩坐中軍帳,C++想分杯羹?難嘍。咱電子工程師天天跟那針尖大的內存空間較勁,C++那些花里胡哨的玩意兒,在這兒真玩不轉。先說內存這道坎兒。您當stm32f4的256kRAM
uCOS III v3.08.01 移植PC Dev C++ 免虛擬機移植WinXP,Win7,Win10,Win 11
uCOS III v3.08.01 移植PC Dev C++ 免虛擬機移植WinXP,Win7,Win10,Win 11。32位系統64位系統都可以。
這里有源碼和程序,歡迎下載測試
發表于 04-15 20:14
C++中的背包問題說明和源碼示例
評論