背包問題思路

1、背包問題思路背包問題思路[問題描述問題描述]在M件物品取出若干件放在空間為W的背包里，每件物品的重量為W1，W2……Wn，與之相對應(yīng)的價值為P1P2……Pn。求出獲得最大價值的方案。注意：在本題中，所有的重量值均為整數(shù)?？梢钥闯鋈绻ㄟ^第N次選擇得到的是一個最優(yōu)解的話，那么第N1次選擇的結(jié)果一定也是一個最優(yōu)解。這符合動態(tài)規(guī)劃中最優(yōu)子問題的性質(zhì)?？紤]用動態(tài)規(guī)劃的方法來解決，這里的：階段是：在前N件物品中，選取若干件物品放入背包中；狀態(tài)是：

2、在前N件物品中，選取若干件物品放入所?？臻g為W的背包中的所能獲得的最大價值；決策是：第N件物品放或者不放；由此可以寫出動態(tài)轉(zhuǎn)移方程：我們用f[ij]表示在前i件物品中選擇若干件放在所?？臻g為j的背包里所能獲得的最大價值f[ij]=maxf[i1jWi]Pi(j=Wi)f[i1j]這樣，我們可以自底向上地得出在前M件物品中取出若干件放進背包能獲得的最大價值，也就是f[mw]算法設(shè)計如下：f(i=1i=v[i])x=f[i1][jv[i]]

3、p[i]if(xf[i][j])f[i][j]=x【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，Mintmain()FILEfpfloatf[101][1001]=0p[101]=0inttmw[101]=0ijfp=fopen(“tw1.in““r“)fscanf(fp“%d%d“f(i=1i=mi)fscanf(fp“%d%f“fclose(fp)fp=fopen(“tw1.out““w“)f(i=1i=mi)f(j=1j=tj)f[i][j]=f