皮肤做了激光手术:0-1 背包问题的动态规划解法@Java实现 Source ForgeT Source F...

来源：百度文库编辑：偶看新闻时间：2024/05/01 08:28:55

0-1 背包问题的动态规划解法@Java实现

分类:Source ForgeTpublic class Knapsack
{
   public static void knapsack(int[] v, int[] w, int c, int[][] m)
   {
       /** v[] w[] c 分别是价值、重量、和背包容量数组
       m[i][j]表示有i~n个物品，背包容量为j的最大价值。*/

       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时的最大价值
       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)
   {// 根据最优值求出最优解
       int n = w.length-1;
       for(int i = 0; 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           System.out.println(xx[i]);
   }
}
// 结果输出bestw=15 最优解为1 1 0 0 1

我需要一个动态规划0/1背包问题的源程序，大家帮帮忙吧!谢谢！如何用0-1背包问题说明贪心算法与动态规划算法的主要区别? 我需要用动态规划解决0/1背包问题的程序请高手帮帮忙吧！用0-1背包问题为例比较动态规划算法、回溯法和分支限界法的区别? 数据结构JAVA版的背包问题动态规划算法相关问题？动态规划求最短路径问题? 求动态规划装箱问题 0/1背包问题的LC分枝-限界法背包的防盗问题？相遇问题的解法动态规划关于Jansport背包的问题动态规划及求解非线性整数规划的现状动态规划的状态转移方程动态规划的讲解和经典题目动态规划的空间效率分析哪儿有关于动态规划的资料？求一动态规划的算法思路柳卡问题的解法动点问题的解法一道化学问题的解法用分支限界法解0/1背包问题用分支限界法求解0/1背包问题