背包問題的java代碼,背包問題的java代碼是什么

_'>回溯法解決0-1背包問題 java寫的 求大神指點(diǎn)~~~~(>_

因?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)建站專注于華寧企業(yè)網(wǎng)站建設(shè),成都響應(yīng)式網(wǎng)站建設(shè)公司,成都商城網(wǎng)站開發(fā)。華寧網(wǎng)站建設(shè)公司,為華寧等地區(qū)提供建站服務(wù)。全流程定制網(wǎng)站，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)建站專業(yè)和態(tài)度為您提供的服務(wù)

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）

關(guān)于這個(gè)java語言描述的0-1背包問題是否有錯(cuò)誤？

有點(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;

}

0-1背包問題java代碼

import?java.io.BufferedInputStream;

import?java.util.Scanner;

public?class?test?{

public?static?int[]?weight?=?new?int[101];

public?static?int[]?value?=?new?int[101];

public?static?void?main(String[]?args)?{

Scanner?cin?=?new?Scanner(new?BufferedInputStream(System.in));

int?n?=?cin.nextInt();

int?W?=?cin.nextInt();

for?(int?i?=?0;?i??n;?++i)?{

weight[i]?=?cin.nextInt();

value[i]?=?cin.nextInt();

}

cin.close();

System.out.println(solve(0,?W,?n));?//?普通遞歸

System.out.println("=========");

System.out.println(solve2(weight,?value,?W));?//?動(dòng)態(tài)規(guī)劃表

}

public?static?int?solve(int?i,?int?W,?int?n)?{

int?res;

if?(i?==?n)?{

res?=?0;

}?else?if?(W??weight[i])?{

res?=?solve(i?+?1,?W,?n);

}?else?{

res?=?Math.max(solve(i?+?1,?W,?n),?solve(i?+?1,?W?-?weight[i],?n)?+?value[i]);

}

return?res;

}

public?static?int?solve2(int[]?weight,?int[]?value,?int?W)?{

int[][]?dp?=?new?int[weight.length?+?1][W?+?1];

for?(int?i?=?weight.length?-?1;?i?=?0;?--i)?{

for?(int?j?=?W;?j?=?0;?--j)?{

dp[i][j]?=?dp[i?+?1][j];?//?從右下往左上，i+1就是剛剛記憶過的背包裝到i+1重量時(shí)的最大價(jià)值

if?(j?+?weight[i]?=?W)?{?//?dp[i][j]就是背包已經(jīng)裝了j的重量時(shí)，能夠獲得的最大價(jià)值

dp[i][j]?=?Math.max(dp[i][j],?value[i]?+?dp[i?+?1][j?+?weight[i]]);

//?當(dāng)背包重量為j時(shí)，要么沿用剛剛裝的，本次不裝，最大價(jià)值dp[i][j]，要么就把這個(gè)重物裝了，那么此時(shí)背包裝的重量為j+weight[i]，

//?用本次的價(jià)值value[i]加上背包已經(jīng)裝了j+weight[i]時(shí)還能獲得的最大價(jià)值，因?yàn)槭菑牡紫峦?，剛剛上一步算過，可以直接用dp[i+1][j+weight[i]]。

//?然后選取本次不裝weight[i]重物時(shí)獲得的最大價(jià)值以及本次裝weight[i]重物獲得的最大價(jià)值兩者之間的最大值

}

}

}

return?dp[0][0];

}

}

分享標(biāo)題：背包問題的java代碼,背包問題的java代碼是什么
當(dāng)前鏈接：http://muchs.cn/article46/hcgjhg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護(hù)、電子商務(wù)、Google、網(wǎng)站設(shè)計(jì)公司、軟件開發(fā)、網(wǎng)站內(nèi)鏈

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)