SHARE
TWEET

Untitled

a guest Jan 14th, 2020 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2.  
  3. class Knapsack
  4. {
  5.  
  6.     static double max(double a, double b) { return (a > b)? a : b; }
  7.  
  8.     // Returns the maximum value that can be put in a knapsack of capacity W
  9.     static ArrayList<Double> knapSack(double W, double wt[])
  10.     {
  11.         W*= 100;
  12.         int n = wt.length;
  13.         for (int i = 0; i < wt.length; i++)
  14.         {
  15.             wt[i] *= 100;
  16.         }
  17.         int K[][] = new int[n+1][(int)W+1];
  18.  
  19.         // Build table K[][] in bottom up manner
  20.         for (int i = 0; i <= n; i++)
  21.         {
  22.             for (int w = 0; w <= W; w++)
  23.             {
  24.                 if (i==0 || w==0)
  25.                     K[i][w] = 0;
  26.                 else if (wt[i-1] <= w)
  27.                     K[i][w] = (int) max(wt[i-1] + K[i-1][(int) (w-wt[i-1])],  K[i-1][w]);
  28.                 else
  29.                     K[i][w] = K[i-1][w];
  30.             }
  31.         }
  32.         return output(K,n,(int)W,wt);
  33.  
  34.     }
  35.     private static ArrayList<Double> output(int[][] K, int n, int W, double[] wt)
  36.     {
  37.         ArrayList<Double> out = new ArrayList<Double>();
  38.         int res = K[n][W];
  39.         int w = W;
  40.         for (int i = n; i > 0 && res > 0; i--) {
  41.  
  42.             // either the result comes from the top
  43.             // (K[i-1][w]) or from (val[i-1] + K[i-1]
  44.             // [w-wt[i-1]]) as in Knapsack table. If
  45.             // it comes from the latter one/ it means
  46.             // the item is included.
  47.             if (res == K[i - 1][w])
  48.                 continue;
  49.             else {
  50.  
  51.                 // This item is included.
  52.                 out.add(wt[i - 1]/100);
  53.  
  54.                 // Since this weight is included its
  55.                 // value is deducted
  56.                 res = (int) (res - wt[i - 1]);
  57.                 w = (int) (w - wt[i - 1]);
  58.             }
  59.         }
  60.         return out;
  61.     }
  62.  
  63.  
  64.  
  65.     public static void main(String args[])
  66.     {
  67.         //[2.5, 4.0, 11.5, 7.0, 15.0, 4.0, 6.0, 8.0]
  68.         double wt[] = new double[]{2.5, 4.0, 11.5, 7.0, 15.0, 4.0, 6.0, 8.0};
  69.         double  W = 6.5;
  70.         int n = wt.length;
  71.         System.out.println(knapSack(W, wt));
  72.     }
  73. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top