• API
• FAQ
• Tools
• Archive
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.
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.
Top