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

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

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

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

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

5、( 1,2, , )0,ii x i ni? ? ? ? ?A A A 表示將第種物品裝入包中表示不將第種物品裝入包于是此問題的數(shù)學(xué)模型為：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 個(gè)物品} elsec[i][j]=c[i-1][j];//剩余容量不夠}//endfor}//endfor cout0;i--){if (c[i][temp_wei]==c[i-1][temp_wei])//最后一個(gè)肯定是最大價(jià)值的{x[i]=0;}else{x[i]=1;temp_wei-=w[i];}} cout<<“應(yīng)裝入的物品有：“;for (i=0;i<=n;i++){if (x[i]){cout&