其中f(i, j)前面i個商品在背包容量為j的情況下達到的最大的價值；weight[i]是第i件商品的重量；PRize[i]是商品的價值。也就是在現在這個背包大小情況下在選擇還是不選擇當前商品中求取總價值最大化。本文中使用較為經典的方式（使用中間表）來解決該問題。這是本文中測試數據得到的中間表：
該表的創建順序是：從上往下，從左往右創建的。表中0~10的數字代表的是背包的容量，背包容量在增長的過程中，最大化背包中商品的價值。舉個栗子：表中價格為3，大小為2開始表格往上生長；直到遇到商品大小為2，價值為6的商品時經過最大化比較背包中九堡原來的商品換成了價值為6，大小為2的商品了。后面的情況也是一次類推的。在實現了中間表的創建之后，接下來的工作就是要尋找到撞到背包中的商品了，尋找商品的過程也是通過這張表來實現的。
在尋找背包中商品的過程中，首先從表的右上角開始尋找（因為那個地方的價值是最大的）。開始設置背包的容量是滿額的（即為10），減去上面紅色標記15對應商品的價值（即為6），且因為最大價值哪行商品已經被統計了，因而開始向下走則就找到上表中紅色標記為9的上方那塊位置，其中也滿足條件兩個位置之間的價值差是選擇了的商品的價值。因而價值為6大小為4的商品被選中。接下來尋找第二個商品，由于原本尋找到的第二個商品（紅色標記為9上方那個商品）對應的背包余量減去改行商品的大小后，簡直不能滿足，因而往下移一行。大體的流程是這樣的。為本表述恐有不明了之處，請查看代碼和推敲很快便能得出其緣由。//構造函數1CPackage01_Problem::CPackage01_Problem(){ this->m_ItemCount = 5; unsigned int price[] = {3, 4, 6, 5, 6}; unsigned int size[] = {2, 5, 2, 6, 4}; this->m_pItemPrice = new unsigned int[this->m_ItemCount]; this->m_pItemSize = new unsigned int[this->m_ItemCount]; for (unsigned int i=0; i<this->m_ItemCount; i++) { this->m_pItemPrice[i] = price[i]; this->m_pItemSize[i] = size[i]; } this->m_PackageSize = 10;}//構造函數2CPackage01_Problem::CPackage01_Problem(unsigned int* ItemPrice, unsigned int ItemCount, unsigned int* ItemSize, unsigned int PackageSize){}CPackage01_Problem::~CPackage01_Problem(){ if (nullptr != this->m_pItemPrice) { delete[] this->m_pItemPrice; this->m_pItemPrice = nullptr; } if (nullptr != this->m_pItemSize) { delete[] this->m_pItemSize; this->m_pItemSize = nullptr; }}unsigned int CPackage01_Problem::Get01_Result(){ unsigned int* m_PackageMatrix = new unsigned int[this->m_ItemCount*(this->m_PackageSize+1)]; //定義 memset(m_PackageMatrix, 0, sizeof(unsigned int)*this->m_ItemCount*(this->m_PackageSize+1)); //清零 unsigned int m_cols = this->m_PackageSize+1; for (unsigned int i=1; i<=this->m_PackageSize; i++) { for (unsigned int j=0; j<this->m_ItemCount; j++) { if (i < this->m_pItemSize[j]) { if (0 == j) { m_PackageMatrix[j*(this->m_PackageSize+1) + i] = 0; } else { m_PackageMatrix[j*m_cols + i] = m_PackageMatrix[(j-1)*m_cols + i]; } } //背包太小了裝不下該商品 else { unsigned int temp_value(0); if (0 == j) { m_PackageMatrix[j*m_cols + i] = this->m_pItemPrice[j]; continue; } //第一個商品可以放入背包,之前背包中沒有東西先放進去再說，不是價值最大的就回溯 else { temp_value = m_PackageMatrix[(j - 1)*m_cols + i - this->m_pItemSize[j]] + this->m_pItemPrice[j]; } m_PackageMatrix[j*m_cols + i] = temp_value > m_PackageMatrix[(j-1)*m_cols + i] ? temp_value : m_PackageMatrix[(j-1)*m_cols + i]; } //背包的容量可以裝下該商品了， } //選區的商品變化 } //背包容量變化 for (unsigned int i = 0; i < this->m_ItemCount; i++) { for (unsigned int j = 0; j <= this->m_PackageSize; j++) { std::cout << m_PackageMatrix[i*m_cols + j] <<" "; } std::cout << std::endl; } //打印中間矩陣 //尋找背包問題的解 unsigned int packagesize = this->m_PackageSize; //獲取背包的體積 cout << "/t價格" << "/t大小" << endl; for (unsigned int i=this->m_ItemCount-1; i>=0; i--) { if (packagesize == 0) { break; } //余量為0了退出 if (i == 0 && packagesize > 0) { cout << "/t" << this->m_pItemPrice[i] << "/t" << this->m_pItemSize[i] << endl; break; } //找到了最后一個商品但是還有余量 則添加進結果 unsigned pos = (packagesize -this->m_pItemSize[i]) < 0? 0:(packagesize -this->m_pItemSize[i]); //防止尋址越界 if (m_PackageMatrix[i*m_cols + packagesize] - m_PackageMatrix[(i-1)*m_cols + pos] == this->m_pItemPrice[i]) { cout << "/t" << this->m_pItemPrice[i] << "/t" << this->m_pItemSize[i] << endl; packagesize -= this->m_pItemSize[i]; } //當前商品對應重量余量 減去 該商品的上一個商品對應背包容量（當前容量減去當前商品大小） //對應的價格等于現在商品的價格時既是需要尋找的商品 } delete[] m_PackageMatrix; m_PackageMatrix = nullptr; return 0;}#pragma once//O1背包問題class CPackage01_Problem{public: CPackage01_Problem(); CPackage01_Problem(unsigned int* ItemPrice, unsigned int ItemCount, unsigned int* ItemSize, unsigned int PackageSize); ~CPackage01_Problem();private: unsigned int* m_pItemPrice; //商品的單價數組 unsigned int* m_pItemSize; //商品的重量 unsigned int m_ItemCount; //商品的總數目 unsigned int m_PackageSize; //背包的大小public: unsigned int Get01_Result();};3. 結果
新聞熱點
疑難解答
