背包問(wèn)題思路

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

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

3、p[i]if(xf[i][j])f[i][j]=x【數(shù)據(jù)規(guī)模】對(duì)于30%的數(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