public class beibao {public int [][] pack(int m,int n,int w[],int p[]){//c[i][v]表示前i件物品恰放入一個重量為m的背包可以獲得的最大價值int c[][]= new int[n+1][m+1];for(int i = 0;i<n+1;i++)c[i][0]=0;for(int j = 0;j<m+1;j++)c[0][j]=0;//for(int i = 1;i<n+1;i++){for(int j = 1;j<m+1;j++){//當物品為i件重量為j時，如果第i件的重量(w[i-1])小于重量j時，c[i][j]為下列兩種情況之一：//(1)物品i不放入背包中，所以c[i][j]為c[i-1][j]的值//(2)物品i放入背包中，則背包剩余重量為j-w[i-1],所以c[i][j]為c[i-1][j-w[i-1]]的值加上當前物品i的價值if(w[i-1]<=j){if(c[i-1][j]<(c[i-1][j-w[i-1]]+p[i-1]))c[i][j] = c[i-1][j-w[i-1]]+p[i-1];elsec[i][j] = c[i-1][j];}elsec[i][j] = c[i-1][j];}}return c;}/*** 逆推法求出最優解* @param c* @param w* @param m* @param n* @return*/public int[] printPack(int c[][],int w[],int m,int n){int x[] = new int[n];//從最后一個狀態記錄c[n][m]開始逆推for(int i = n;i>0;i--){//如果c[i][m]大于c[i-1][m]，說明c[i][m]這個最優值中包含了w[i-1](注意這里是i-1，因為c數組長度是n+1)if(c[i][m]>c[i-1][m]){x[i-1] = 1;m-=w[i-1];}}for(int j = 0;j<n;j++)System.out.println(x[j]);return x;}public static void main(String args[]){int m = 10;int n = 3;int w[]={3,4,5};int p[]={4,5,6};beibao pack = new beibao();int c[][] = pack.pack(m, n, w, p);pack.printPack(c, w, m,n);}}

總結

以上是生活随笔為你收集整理的01背包java 源码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。