0-1 背包問(wèn)題的動(dòng)態(tài)規劃解法@Java實(shí)現 Source ForgeT Source F...
0-1 背包問(wèn)題的動(dòng)態(tài)規劃解法@Java實(shí)現
public class Knapsack
{
public static void knapsack(int[] v, int[] w, int c, int[][] m)
{
/** v[] w[] c 分別是價(jià)值、重量、和背包容量數組
m[i][j]表示有i~n個(gè)物品，背包容量為j的最大價(jià)值。*/
int n = v.length-1;
int jMax = Math.min(w[n]-1, c);
for(int j = 0; j <= jMax; j++)
m[n][j] = 0; //當w[n]>j 有 m[n][j]=0
//m[n][j] 表示只有n物品，背包的容量為j時(shí)的最大價(jià)值
for (int l = w[n]; l <= c; l++)
m[n][l] = v[n]; //當w[n]<=j 有m[n][j]=v[n]
//遞規調用求出m[][]其它值，直到求出m[0][c]
for(int i = n-1; i >=1; i--)
{
jMax = Math.min(w[i]-1,c);
for(int k = 0; k <=jMax; k++)
m[i][k] = m[i+1][k];
for(int h = w[i]; h <= c; h++)
m[i][h] = Math.max(m[i+1][h],m[i+1][h-w[i]]+v[i]);
}
m[0][c] = m[1][c];
if(c >= w[0])
m[0][c] = Math.max(m[0][c],m[1][c-w[0]]+v[0]);
System.out.println("bestw ="+m[0][c]);
}
public static void traceback(int[][] m, int[] w, int c, int[] x)
{// 根據最優(yōu)值求出最優(yōu)解
int n = w.length-1;
for(int i = 0; i<n;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;
}
public static void main(String[] args)
{
//測試
int[] ww = {2,2,6,5,4};
int[] vv = {6,3,5,4,6};
int[][] mm = new int[11][11];
knapsack(vv,ww,10,mm);
int[] xx =new int[ww.length];
traceback(mm,ww,10,xx);
for(int i = 0;i<xx.length;i++)
System.out.println(xx[i]);
}
}
// 結果輸出bestw=15 最優(yōu)解為1 1 0 0 1
本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請
點(diǎn)擊舉報。
