uopspop

Untitled

Oct 5th, 2019
137
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Stack;
  2.  
  3. public class DP_Knapsack_repetition {
  4.  
  5.     public static void main(String[] args) {
  6.  
  7.         int w[] = new int[]{6,3,4,2};
  8.         int v[] = new int[]{30,14,16,9};
  9.  
  10.         int max_w = 10;
  11.  
  12.         Integer result = dp_knapsack_repitition(w, v, max_w);
  13.         System.out.println("result:" + result);
  14.         System.out.println();
  15.     }
  16.  
  17.     private static int dp_knapsack_repitition(int[] w, int[] v, int max_w) {
  18.         int value = 0;
  19.  
  20.         int best_val[] = new int[max_w + 1]; // attention: we intend to allow from 0 ~ 10 (11 numbers instead of 10 numbres)
  21.         int parent[] = new int[max_w + 1];
  22.         int itemPicked[] = new int[max_w + 1];
  23.  
  24.         // initialize the array
  25.         for (int i = 0; i < best_val.length; i++) {
  26.             best_val[i] = 0;
  27.         }
  28.  
  29.         // set the base state
  30.         best_val[0] = 0; // when the total allowed weight is zero, of course, the value is zero
  31.  
  32.         for (int nowW = 1; nowW < best_val.length; nowW++) {
  33.  
  34.             // get the max value and weight
  35.             int bestValThisRun = 0; // to decide picking wich item will produce the best value
  36.  
  37.             for (int itemIndex = 0; itemIndex < w.length; itemIndex++) {
  38.                 if (w[itemIndex] <= nowW) { // if less than affordable weight, we pick it as one of the tries
  39.                     int tmpVal = v[itemIndex] + best_val[nowW - w[itemIndex]];
  40.                     if (tmpVal > bestValThisRun) {
  41.                         bestValThisRun = tmpVal;
  42.                         parent[nowW] = nowW - w[itemIndex];
  43.                         itemPicked[nowW] = itemIndex;
  44.                     }
  45.                 }
  46.             } // end of for
  47.  
  48.             // update the best_val for later use
  49.             best_val[nowW] = bestValThisRun;
  50.         }
  51.  
  52.         System.out.println("best_val: ");
  53.         printArray(best_val);
  54.  
  55.         System.out.println("parent: ");
  56.         printArray(parent);
  57.  
  58.         // print the dag
  59.         int nowWeightIndex = max_w;
  60.         while(true) {
  61.             int nowItemIndex = itemPicked[nowWeightIndex];
  62.             System.out.printf("(%d) - picked item# %d w:%d v:%d%n", nowWeightIndex, nowItemIndex, w[nowItemIndex], v[nowItemIndex]);
  63.             nowWeightIndex = parent[nowWeightIndex];
  64.             if (nowWeightIndex == 0) break;
  65.         }
  66.  
  67.         value = best_val[max_w];
  68.         return value;
  69.     }
  70.  
  71.     private static void printArray(int[] array) {
  72.         for (int i = 0; i < array.length; i++) {
  73.             System.out.print(" ");
  74.             System.out.print(array[i]);
  75.         }
  76.         System.out.println();
  77.     }
  78. }
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.

×