數(shù)學建模背包問題

1、背包問題 背包問題背包問題(Knapsack problem)是一種組合優(yōu)化的 NP 完全問題。問題可以描 述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內， 我們如何選擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合 適的物品放置于給定背包中。相似問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學，計算復雜 性理論、密碼學和應用數(shù)學等領域中。也可以將背包問題描述為決定性問題， 即在總重量不超過 W 的前提下，總價值是否能達到 V

2、？它是在 1978 年由 Merkel 和 Hellman 提出的 一、定義：背包問題屬于組合優(yōu)化問題，一般的最優(yōu)化問題由目標函數(shù)和約束條件兩 部部分組成：我們有 n 種物品，物品 i 的重量為 wi，價格為 pi。我們假定所有物品的重 量和價格都是非負的。背包所能承受的最大重量為 W。如果限定每種物品只能選擇 0 個或 1 個，則問題稱為 0-1 背包問題 背包問題?？梢?用公式表示為：1maxni iip x? ?1. . ,ni

3、iiS T w x W?? ? ? ? 0,1 i x ?如果限定物品 i 最多只能選擇 bi 個，則問題稱為有界背包問題 有界背包問題。可以用公 式表示為：1maxni iip x? ?1. . ,ni iiS T w x W?? ? ? ? 0,1, , i i x b ? ???如果不限定每種物品的數(shù)量，則問題稱為無界背包問題 無界背包問題。 各類復雜的背包問題總可以變換為簡單的 0-1 背包問題進行求解。二、基本模型的建立方法

4、1、0-1 背包問題的數(shù)學模型（最基礎的背包問題）分類：0-1 背包問題簡單分為一維背包和二維背包問題。 特點：每種物品僅有一件，可以選擇放或不放。1.1 一維背包問題問題：一個旅行者準備進行徒步旅行，為此他必須決定攜帶若干物 品。設有 件物品可供他選擇，編號為 第 件物品重量為 千克， n 1,2,...,n i i w價值為 元，他能攜帶的最大重量為 千克。他應該裝入哪幾件物品價值 i p w最大。解：引入變量 ，且設 i x1,

5、( 1,2, , )0,ii x i ni? ? ? ? ?A A A 表示將第種物品裝入包中表示不將第種物品裝入包于是此問題的數(shù)學模型為：1maxni iif p x?? ?//c(i,j)=max{c(i-1,j), c(i-1,j-w[i])+vl(i)}for (i=1;ic[i-1][j]) {c[i][j]=vl[i]+c[i-1][j-w[i]];//選擇第 i 物品} elsec[i][j]=c[i-1][j];//不選

6、擇第 i 個物品} elsec[i][j]=c[i-1][j];//剩余容量不夠}//endfor}//endfor cout0;i--){if (c[i][temp_wei]==c[i-1][temp_wei])//最后一個肯定是最大價值的{x[i]=0;}else{x[i]=1;temp_wei-=w[i];}} cout<<“應裝入的物品有：“;for (i=0;i<=n;i++){if (x[i]){cout&