国产精品久久久aaaa,日日干夜夜操天天插,亚洲乱熟女香蕉一区二区三区少妇,99精品国产高清一区二区三区,国产成人精品一区二区色戒,久久久国产精品成人免费,亚洲精品毛片久久久久,99久久婷婷国产综合精品电影,国产一区二区三区任你鲁

0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

C++中的背包問題說明和源碼示例

C語言編程學(xué)習(xí)基地 ? 來源:C語言編程學(xué)習(xí)基地 ? 作者:C語言編程學(xué)習(xí)基地 ? 2021-10-12 09:27 ? 次閱讀
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

問題說明

有N件物品和一個(gè)容量為V的背包。

第i件物品的重量是w[i],價(jià)值是v[i]。

求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量,

且價(jià)值總和最大。

功能說明

本程序用動態(tài)規(guī)劃的思想解決了背包問題,并用了兩種算法:迭代法、遞歸法。在迭代法中實(shí)現(xiàn)了打印背包問題的表格。

代碼簡述

通過用戶輸入數(shù)據(jù),程序輸入檢測,動態(tài)分配空間,選擇算法, 用動態(tài)規(guī)劃的思想求解背包問題。

迭代法:

通過遍歷n行W列,迭代每行每列的值,并把最優(yōu)解放到 n行(在數(shù)組中為第n+1行)W列(在數(shù)組中為第W+1列)中。

遞歸法:

通過每次返回前i個(gè)物品和承重為j的最優(yōu)解, 遞歸計(jì)算總背包問題的最優(yōu)解。

源碼示例

#include #include using namespace std;
int **T = NULL;    // 存儲背包問題表格的數(shù)組指針
// 返回兩個(gè)值的最大值int max(int a, int b) {  return (a > b) ? a : b;}
// 迭代法,能顯示背包問題的表格int packIterative(int n, int W, int *w, int *v) {    // 循環(huán)遍歷n行  for (int i = 1; i <= n; ++i)  {    // 循環(huán)遍歷W列    for (int j = 1; j <= W; ++j)    {      //第i個(gè)物品能裝下,則比較包括第i個(gè)物品和不包括第i個(gè)物品,取其最大值      if (w[i] <= j)        T[i][j] = max(v[i] + T[i - 1][j - w[i]], T[i - 1][j]);
      // 第i個(gè)物品不能裝下,則遞歸裝i-1個(gè)      else        T[i][j] = T[i - 1][j];    }  }  return T[n][W];}
// 遞歸法,不支持顯示背包問題的表格int packRecursive(int n, int W, int *w, int *v) {  // 結(jié)束條件(初始條件),i或者j為0時(shí)最大總價(jià)值為0  if (n == 0 || W == 0) {    return 0;  }  // 第i個(gè)物品不能裝下,則遞歸裝i-1個(gè)  if (w[n] > W) {    return packRecursive(n - 1, W, w, v);  }  //第i個(gè)物品能裝下,則比較包括第i個(gè)物品和不包括第i個(gè)物品,取其最大值  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++)  {    // 打印行數(shù)    cout << i << ":	";
    // 打印W列    for (int w = 0; w <= W; w++)    {      cout << T[i][w] << "	";    }
    // 換行    cout << endl;  }}
int main() {  int *w = NULL;    // 存儲每件物品重量的數(shù)組指針  int *v = NULL;    // 存儲每件物品價(jià)值的數(shù)組指針  int n;        // 物品個(gè)數(shù)n  int W;        // 背包總承重W
  cout << "---------------- 背包問題 ----------------" << endl;  cout << "請輸入物品數(shù) n (n>=0) " << endl;
  // 輸入背包數(shù)  cin >> n;
  if (cin.fail() || n < 0)  {    cout << "輸入n錯(cuò)誤!" << endl;    system("pause");    return 0;  }
  cout << "請輸入背包承重量 W (W>=0) " << endl;
  // 輸入背包承重量  cin >> W;
  if (cin.fail() || W < 0)  {    cout << "輸入W錯(cuò)誤!" << endl;    system("pause");    return 0;  }
  // 分配空間  // 對w和v分配n+1大小  w = new int[n + 1];  v = new int[n + 1];
  // 對T分配n+1行,并初始化為0  T = new int *[n + 1]();  // 對T分配W+1列,并初始化為0  for (auto i = 0; i <= n; i++)  {    T[i] = new int[W + 1]();  }
  // 輸入背包的重量和價(jià)值  for (auto i = 1; i <= n; i++)  {    cout << "請輸入第 " << i << " 個(gè)物品的重量和價(jià)值(用空格隔開)" << endl;    cin >> w[i] >> v[i];    if (cin.fail() || w[i] < 0 || v[i] < 0)    {      cout << "輸入錯(cuò)誤!" << 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 << "能裝下物品的最大價(jià)值為 " << packIterative(n, W, w, v) << endl;    cout << "------------------------------------------------" << endl;    printT(n, W);    break;  }  case 2:  {    // 遞歸法,不支持顯示背包問題的表格    cout << "能裝下物品的最大價(jià)值為 " << packRecursive(n, W, w, v) << endl;    break;  }  default:  {    cout << "輸入錯(cuò)誤!" << endl;    break;  }  }
  cout << "------------------------------------------------" << endl;
  delete w;  delete v;  for (int i = 0; i <= n; ++i) {    delete[] T[i];  }  delete[] T;
  system("pause");  return 0;}

今天的分享就到這里了,大家要好好學(xué)C++喲~

責(zé)任編輯:haq
聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報(bào)投訴
  • 數(shù)據(jù)
    +關(guān)注

    關(guān)注

    8

    文章

    7335

    瀏覽量

    94757
  • C++
    C++
    +關(guān)注

    關(guān)注

    22

    文章

    2124

    瀏覽量

    77110

原文標(biāo)題:C++經(jīng)典算法問題:背包問題(迭代+遞歸算法)!含源碼示例

文章出處:【微信號:cyuyanxuexi,微信公眾號:C語言編程學(xué)習(xí)基地】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。

收藏 人收藏
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

    評論

    相關(guān)推薦
    熱點(diǎn)推薦

    CW32系列MCU在Eclipse GCC + JLink下的使用示例分享

    CW32系列MCU在Eclipse GCC + JLink下的使用示例: 1、下載安裝Eclipse IDE for Embedded C/C++ Developers。 2、下載安裝
    發(fā)表于 02-02 06:57

    keil實(shí)現(xiàn)cc++混合編程

    起因項(xiàng)目中使用到一個(gè)開源的模擬IIC的庫,封裝的比較好,但是是使用c++寫的。于是將其移植到自己的項(xiàng)目中,主要有以下三步操作: 在工程選項(xiàng) C/C++中去掉勾選
    發(fā)表于 01-26 08:58

    C語言與C++的區(qū)別及聯(lián)系

    缺點(diǎn):性能比面向過程低。 二、具體語言上的區(qū)別 1、關(guān)鍵字的不同 C語言有32個(gè)關(guān)鍵字;C++有63個(gè)關(guān)鍵字。 2、后綴名不同 C源文件后綴.c
    發(fā)表于 12-24 07:23

    CC++之間的聯(lián)系

    1、語法兼容性: C++完全兼容C語言的語法,這意味著任何有效的C語言程序都可以直接在C++編譯器下編譯通過。 2、底層控制: C++
    發(fā)表于 12-11 06:51

    C語言和C++之間的區(qū)別是什么

    區(qū)別 1、面向?qū)ο缶幊?(OOP): C語言是一種面向過程的語言,它強(qiáng)調(diào)的是通過函數(shù)將任務(wù)分解為一系列步驟進(jìn)行執(zhí)行。 C++C語言的基礎(chǔ)上擴(kuò)展了面向?qū)ο蟮奶匦裕С诸?class)、封裝、繼承
    發(fā)表于 12-11 06:23

    C/C++條件編譯

    條件編譯是一種在編譯時(shí)根據(jù)條件選擇性地包含或排除部分代碼的處理方法。在 C/C++ ,條件編譯使用預(yù)處理指令 #ifdef、#endif、#else 和 #elif 來實(shí)現(xiàn)。常用的條件編譯指令有
    發(fā)表于 12-05 06:21

    C++程序異常的處理機(jī)制

    1、什么是異常處理? 有經(jīng)驗(yàn)的朋友應(yīng)該知道,在正常的CC++編程過程難免會碰到程序不按照原本設(shè)計(jì)運(yùn)行的情況。 最常見的有除法分母為零,數(shù)組越界,內(nèi)存分配失效、打開相應(yīng)文件失敗等等。 一個(gè)程序
    發(fā)表于 12-02 07:12

    C/C++代碼靜態(tài)測試工具Perforce QAC 2025.3的新特性

    ?Perforce Validate??QAC?項(xiàng)目的相對/根路徑的支持。C++?分析也得到了增強(qiáng),增加了用于檢測 C++?并發(fā)問題的新檢查,并改進(jìn)了實(shí)體名稱和實(shí)
    的頭像 發(fā)表于 10-13 18:11 ?571次閱讀
    <b class='flag-5'>C</b>/<b class='flag-5'>C++</b>代碼靜態(tài)測試工具Perforce QAC 2025.3的新特性

    技能+1!如何在樹莓派上使用C++控制GPIO?

    和PiGPIO等庫,C++可用于編程控制樹莓派的GPIO引腳。它提供了更好的性能和控制能力,非常適合對速度和精度要求較高的硬件項(xiàng)目。在樹莓派社區(qū),關(guān)于“Python
    的頭像 發(fā)表于 08-06 15:33 ?4151次閱讀
    技能+1!如何在樹莓派上使用<b class='flag-5'>C++</b>控制GPIO?

    請問如何在C++中使用NPU上的模型緩存?

    無法確定如何在 C++ 的 NPU 上使用模型緩存
    發(fā)表于 06-24 07:25

    在OpenVINO? C++代碼啟用 AddressSanitizer 時(shí)的內(nèi)存泄漏怎么解決?

    在 OpenVINO? C++代碼啟用 AddressSanitizer 時(shí)遇到內(nèi)存泄漏: \"#0 0xaaaab8558370 in operator new(unsigned
    發(fā)表于 06-23 07:16

    基于stm32 nucleo_L476的智能燈(操作說明+源碼

    基于stm32 nucleo_L476的智能燈(操作說明+源碼)推薦下載!
    發(fā)表于 05-28 21:29

    主流的 MCU 開發(fā)語言為什么是 C 而不是 C++

    在單片機(jī)的地界兒里,C語言穩(wěn)坐中軍帳,C++想分杯羹?難嘍。咱電子工程師天天跟那針尖大的內(nèi)存空間較勁,C++那些花里胡哨的玩意兒,在這兒真玩不轉(zhuǎn)。先說內(nèi)存這道坎兒。您當(dāng)stm32f4的256kRAM
    的頭像 發(fā)表于 05-21 10:33 ?1040次閱讀
    主流的 MCU 開發(fā)語言為什么是 <b class='flag-5'>C</b> 而不是 <b class='flag-5'>C++</b>?

    uCOS III v3.08.01 移植PC Dev C++ 免虛擬機(jī)移植WinXP,Win7,Win10,Win 11

    uCOS III v3.08.01 移植PC Dev C++ 免虛擬機(jī)移植WinXP,Win7,Win10,Win 11。32位系統(tǒng)64位系統(tǒng)都可以。 這里有源碼和程序,歡迎下載測試
    發(fā)表于 04-15 20:14

    創(chuàng)建了用于OpenVINO?推理的自定義C++和Python代碼,從C++代碼獲得的結(jié)果與Python代碼不同是為什么?

    創(chuàng)建了用于OpenVINO?推理的自定義 C++ 和 Python* 代碼。 在兩個(gè)推理過程中使用相同的圖像和模型。 從 C++ 代碼獲得的結(jié)果與 Python* 代碼不同。
    發(fā)表于 03-06 06:22