uopspop

Untitled

Oct 5th, 2019
151
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class DP_Knapsack_Norepetition {
  2.  
  3.     public static void main(String[] args) {
  4.  
  5.         int w[] = new int[]{6,3,4,2};
  6.         int v[] = new int[]{30,14,16,9};
  7.  
  8.         int max_w = 10;
  9.  
  10.         Integer result = dp_knapsack_repitition(w, v, max_w);
  11.         System.out.println("result:" + result);
  12.         System.out.println();
  13.     }
  14.  
  15.     private static int dp_knapsack_repitition(int[] w, int[] v, int max_w) {
  16.         int value = 0;
  17.  
  18.         int best_val[][] = new int[max_w + 1][v.length]; // attention: we intend to allow from 0 ~ 10 (11 numbers instead of 10 numbres)
  19.  
  20.         // initialize the array
  21.         for (int i = 0; i < best_val.length; i++) {
  22.             for (int j = 0; j < best_val[i].length; j++) {
  23.                 best_val[i][j] = -1;
  24.             }
  25.         }
  26.  
  27.         // set the base state -> w = 0
  28.         for (int j = 0; j <best_val[j].length; j++) {
  29.             best_val[0][j] = 0;
  30.         }
  31.  
  32.         System.out.println("base state: ");
  33.         print2DArray(best_val);
  34.  
  35.         for (int nowW = 1; nowW < best_val.length; nowW++) {
  36.  
  37.             for (int itemIndex = 0; itemIndex < w.length; itemIndex++) { // go through each item to try
  38.                 // find the best val
  39.                 int tmpVal = 0;
  40.  
  41.                 if (w[itemIndex] <= nowW && itemIndex == 0) { // if this is the first item and it is ok to take
  42.                     tmpVal = Math.max( 0, v[itemIndex]);
  43.                 }else if (w[itemIndex] <= nowW && itemIndex != 0) {
  44.                     tmpVal = Math.max( best_val[nowW][itemIndex-1], v[itemIndex] + best_val[nowW-w[itemIndex]][itemIndex-1]); // we either pick the current item or not
  45.                 }else if (w[itemIndex] > nowW && itemIndex != 0) {
  46.                     tmpVal = best_val[nowW][itemIndex-1]; // if too heavy, then try the next item for this weight limit
  47.                 }
  48.  
  49.                 best_val[nowW][itemIndex] = tmpVal;
  50.             } // end of inner for // 真正有意義的是當每一輪都到了最後一個item時,我們才知道在某個限重下,最好的組合是怎樣。(中間都只是輔助資訊)
  51.  
  52.         } // end of outer for
  53.  
  54.  
  55.         System.out.println("final state: ");
  56.         print2DArray(best_val);
  57.  
  58.         value = best_val[max_w][v.length-1];
  59.  
  60.         return value;
  61.     }
  62.  
  63.     private static void print2DArray(int[][] ary){
  64.         for (int i = 0; i < ary.length; i++) {
  65.             for (int j = 0; j < ary[i].length; j++) {
  66.                 System.out.printf("%3d" , ary[i][j]);
  67.             }
  68.             System.out.println();
  69.         }
  70.     }
  71. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×