十年網(wǎng)站開發(fā)經(jīng)驗(yàn) + 多家企業(yè)客戶 + 靠譜的建站團(tuán)隊(duì)
量身定制 + 運(yùn)營(yíng)維護(hù)+專業(yè)推廣+無憂售后,網(wǎng)站問題一站解決
因?yàn)槟惆裯和c 定義為static ,而且初始化為0,。數(shù)組也為靜態(tài)的,一個(gè)類中靜態(tài)的變量在這個(gè)類加載的時(shí)候就會(huì)執(zhí)行,所以當(dāng)你這類加載的時(shí)候,你的數(shù)組static int[] v = new int[n];

創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),營(yíng)山企業(yè)網(wǎng)站建設(shè),營(yíng)山品牌網(wǎng)站建設(shè),網(wǎng)站定制,營(yíng)山網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,營(yíng)山網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè),幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力??沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿,時(shí)刻以成就客戶成長(zhǎng)自我,堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己,讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。
static int[] w = new int[n];
就已經(jīng)初始化完畢,而且數(shù)組大小為0。在main方法里動(dòng)態(tài)改變n的值是改變不了已經(jīng)初始化完畢的數(shù)組的大小的,因?yàn)榻M已經(jīng)加載完畢。
我建議你可以在定義n,c是就為其賦初值。比如(static int n=2 static int c=3)
基本概念
問題雛形
01背包題目的雛形是:
有N件物品和一個(gè)容量為V的背包。第i件物品的體積是c[i],價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。
從這個(gè)題目中可以看出,01背包的特點(diǎn)就是:每種物品僅有一件,可以選擇放或不放。
其狀態(tài)轉(zhuǎn)移方程是:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
對(duì)于這方方程其實(shí)并不難理解,方程之中,現(xiàn)在需要放置的是第i件物品,這件物品的體積是c[i],價(jià)值是w[i],因此f[i-1][v]代表的就是不將這件物品放入背包,而f[i-1][v-c[i]]+w[i]則是代表將第i件放入背包之后的總價(jià)值,比較兩者的價(jià)值,得出最大的價(jià)值存入現(xiàn)在的背包之中。
理解了這個(gè)方程后,將方程代入實(shí)際題目的應(yīng)用之中,可得
for (i = 1; i = n; i++)
for (j = v; j = c[i]; j--)//在這里,背包放入物品后,容量不斷的減少,直到再也放不進(jìn)了
f[i][j] = max(f[i - 1][j], f[i - 1][j - c[i]] + w[i]);
問題描述
求出獲得最大價(jià)值的方案。
注意:在本題中,所有的體積值均為整數(shù)。
算法分析
對(duì)于背包問題,通常的處理方法是搜索。
用遞歸來完成搜索,算法設(shè)計(jì)如下:
int make(int i, int j)//處理到第i件物品,剩余的空間為j 初始時(shí)i=m , j=背包總?cè)萘?/p>
{
if (i == 0) return 0;
if (j = c[i])//(背包剩余空間可以放下物品 i )
{
int r1 = make(i - 1, j - w[i]);//第i件物品放入所能得到的價(jià)值
int r2 = make(i - 1, j);//第i件物品不放所能得到的價(jià)值
return min(r1, r2);
}
return make(i - 1, j);//放不下物品 i
}
這個(gè)算法的時(shí)間復(fù)雜度是O(n^2),我們可以做一些簡(jiǎn)單的優(yōu)化。
由于本題中的所有物品的體積均為整數(shù),經(jīng)過幾次的選擇后背包的剩余空間可能會(huì)相等,在搜索中會(huì)重復(fù)計(jì)算這些結(jié)點(diǎn),所以,如果我們把搜索過程中計(jì)算過的結(jié)點(diǎn)的值記錄下來,以保證不重復(fù)計(jì)算的話,速度就會(huì)提高很多。這是簡(jiǎn)單的“以空間換時(shí)間”。
我們發(fā)現(xiàn),由于這些計(jì)算過程中會(huì)出現(xiàn)重疊的結(jié)點(diǎn),符合動(dòng)態(tài)規(guī)劃中子問題重疊的性質(zhì)。
同時(shí),可以看出如果通過第N次選擇得到的是一個(gè)最優(yōu)解的話,那么第N-1次選擇的結(jié)果一定也是一個(gè)最優(yōu)解。這符合動(dòng)態(tài)規(guī)劃中最優(yōu)子問題的性質(zhì)。
解決方案
考慮用動(dòng)態(tài)規(guī)劃的方法來解決,這里的:
階段:在前N件物品中,選取若干件物品放入背包中
狀態(tài):在前N件物品中,選取若干件物品放入所??臻g為W的背包中的所能獲得的最大價(jià)值
決策:第N件物品放或者不放
由此可以寫出動(dòng)態(tài)轉(zhuǎn)移方程:
我們用f[i][j]表示在前 i 件物品中選擇若干件放在已用空間為 j 的背包里所能獲得的最大價(jià)值
f[i][j] = max(f[i - 1][j - W[i]] + P[i], f[i - 1][j]);//j = W[ i ]
這個(gè)方程非常重要,基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細(xì)解釋一下:“將前i件物品放入容量為v的背包中”這個(gè)子問題,若只考慮第i件物品的策略(放或不放),那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問題。如果不放第i件物品,那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”,價(jià)值為f[v];如果放第i件物品,那么問題就轉(zhuǎn)化為“前i-1件物品放入已用的容量為c的背包中”,此時(shí)能獲得的最大價(jià)值就是f[c]再加上通過放入第i件物品獲得的價(jià)值w。
這樣,我們可以自底向上地得出在前M件物品中取出若干件放進(jìn)背包能獲得的最大價(jià)值,也就是f[m,w]
算法設(shè)計(jì)如下:
int main()
{
cin n v;
for (int i = 1; i = n; i++)
cin c[i];//價(jià)值
for (int i = 1; i = n; i++)
cin w[i];//體積
for (int i = 1; i = n; i++)
f[i][0] = 0;
for (int i = 1; i = n; i++)
for (int j = 1; j = v; j++)
if (j = w[i])//背包容量夠大
f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]);
else//背包容量不足
f[i][j] = f[i - 1][j];
cout f[n][v] endl;
return 0;
}
由于是用了一個(gè)二重循環(huán),這個(gè)算法的時(shí)間復(fù)雜度是O(n*w)。而用搜索的時(shí)候,當(dāng)出現(xiàn)最壞的情況,也就是所有的結(jié)點(diǎn)都沒有重疊,那么它的時(shí)間復(fù)雜度是O(2^n)??瓷先デ罢咭旌芏?。但是,可以發(fā)現(xiàn)在搜索中計(jì)算過的結(jié)點(diǎn)在動(dòng)態(tài)規(guī)劃中也全都要計(jì)算,而且這里算得更多(有一些在最后沒有派上用場(chǎng)的結(jié)點(diǎn)我們也必須計(jì)算),在這一點(diǎn)上好像是矛盾的。
有點(diǎn)問題:
public static void knapsack(int[]v,int[]w,int c,int[][]m)
{
int n=v.length-1;
int jMax=Math.min(w[n]-1,c);
for(int j=0;j=jMax;j++)
m[n][j]=0;
for(int j=w[n];j=c;j++)
m[n][j]=v[n];
for(int i=n-1;i1;i--)
{
jMax=Math.min(w[i]-1,c);
for(int j=0;j=jMax;j++)
m[i][j]=m[i+1][j];
for(int j=w[i];j=c;j++)
m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c=w[1])
m[1][c]=Math.max(m[1][c],m[2][c-w[1]]+v[1]);
}
public static void traceback(int[][]m,int[]w,int c,int[]x)
{
int n=w.length-1;
for(int i=1;in;i++) {
if(m[i][c]==m[i+1][c])x[i]=0;
else {
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c]0)?1:0;
}
//int n=w.length-1;
for(int i=1;in;i++)
if(m[i][c]==m[i+1][c])x[i]=0;
else {
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c]0)?1:0;
}