uopspop

Untitled

Oct 5th, 2019
152
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.awt.*;
  2.  
  3. public class DP_Knapsack_Norepetition_CountWeight_Assignment {
  4.  
  5.     public static void main(String[] args) {
  6.  
  7.         int w[] = new int[]{1, 4, 6, 2, 5, 10, 8, 3, 9, 1, 4, 2, 5, 8, 9, 1};
  8.         int v[] = new int[]{ 10, 5, 30, 8, 12, 30, 50, 10, 2, 10, 40, 80, 100, 25, 10, 5 };
  9.         int max_w = 20;
  10.  
  11. //        int w[] = new int[]{6,3,4,2};
  12. //        int v[] = new int[]{30,14,16,9};
  13. //
  14. //        int max_w = 10;
  15.  
  16. //        int w[] = new int[]{11,11,11,2};
  17. //        int v[] = new int[]{30,14,16,9};
  18. //
  19. //        int max_w = 10;
  20.  
  21.  
  22.         dp_knapsack_repitition(w, v, max_w);
  23.         System.out.println();
  24.     }
  25.  
  26.     private static int dp_knapsack_repitition(int[] w, int[] v, int max_w) {
  27.         int best_val[][] = new int[max_w + 1][v.length]; // attention: we intend to allow from 0 ~ 10 (11 numbers instead of 10 numbres)
  28.         int parent_row[][] = new int[max_w + 1][v.length];
  29.         int parent_col[][] = new int[max_w + 1][v.length];
  30.         int iterationCount = 0;
  31.  
  32.         // initialize the array
  33.         for (int i = 0; i <= max_w; i++) {
  34.             for (int j = 0; j < best_val[i].length; j++) {
  35.                 best_val[i][j] = -1;
  36.             }
  37.         }
  38.  
  39.         // set the base state -> w = 0
  40.         for (int itemIndex = 0; itemIndex < v.length; itemIndex++) {
  41.             best_val[0][itemIndex] = 0;
  42.             parent_row[0][itemIndex] = -1; // no parent for the base case
  43.             parent_col[0][itemIndex] = -1; // no parent for the base case
  44.         }
  45.  
  46.         // set the base state -> v = 0 (no item is picked)
  47.         for (int wIndex = 0; wIndex < max_w + 1; wIndex++) {
  48.             best_val[wIndex][0] = 0;
  49.             parent_row[wIndex][0] = -1; // no parent for the base case
  50.             parent_col[wIndex][0] = -1; // no parent for the base case
  51.         }
  52.  
  53.  
  54.         System.out.println("\r\nbase state: ");
  55.         print2DArray(best_val);
  56.  
  57.         for (int nowW = 1; nowW < best_val.length; nowW++) {
  58.  
  59.             for (int itemIndex = 0; itemIndex < w.length; itemIndex++) { // go through each item to try
  60.  
  61.                 // increment iteraiton count
  62.                 iterationCount++;
  63.  
  64.                 // find the best val
  65.                 int tmpVal = 0;
  66.  
  67.                 if (w[itemIndex] <= nowW && itemIndex == 0) { // if this is the first item and it is ok to take
  68.                     tmpVal = Math.max( 0, v[itemIndex]);
  69.                     parent_row[nowW][itemIndex] = nowW - w[itemIndex]; // attention: if picked, the affordable weight will go down
  70.                     parent_col[nowW][itemIndex] = itemIndex;
  71.                 }else if (w[itemIndex] <= nowW && itemIndex != 0) { // if this is not the first item, then we decide whether to pick this one or not
  72.  
  73.                     // get the better one
  74.                     int noPick = best_val[nowW][itemIndex - 1];
  75.                     int pick = v[itemIndex] + best_val[nowW - w[itemIndex]][itemIndex - 1];
  76.  
  77.                     if (noPick > pick){
  78.                         parent_row[nowW][itemIndex] = nowW;
  79.                         parent_col[nowW][itemIndex] = itemIndex - 1;
  80.                     } else {
  81.                         parent_row[nowW][itemIndex] = nowW - w[itemIndex]; // attention: if picked, the affordable weight will go down
  82.                         parent_col[nowW][itemIndex] = itemIndex - 1;
  83.                     }
  84.  
  85.                     tmpVal = Math.max(noPick, pick); // we either pick the current item or not
  86.                 }else if (w[itemIndex] > nowW && itemIndex != 0) {
  87.                     tmpVal = best_val[nowW][itemIndex-1]; // if too heavy, then try the previous item for this weight limit
  88.                     parent_row[nowW][itemIndex] = nowW;
  89.                     parent_col[nowW][itemIndex] = itemIndex - 1;
  90.                 }
  91.  
  92.                 best_val[nowW][itemIndex] = tmpVal;
  93.             } // end of inner for // 真正有意義的是當每一輪都到了最後一個item時,我們才知道在某個限重下,最好的組合是怎樣。(中間都只是輔助資訊)
  94.  
  95.         } // end of outer for
  96.  
  97.  
  98.         System.out.println("\nfinal state: ");
  99.         print2DArray(best_val);
  100.  
  101. //        System.out.println("final row: ");
  102. //        print2DArray(parent_row);
  103. //
  104. //        System.out.println("final col: ");
  105. //        print2DArray(parent_col);
  106.  
  107.         // print parent
  108.         System.out.println("\nThe final route: ");
  109.         int currentRow = max_w;
  110.         int currentCol = v.length-1;
  111.         while(true){
  112.  
  113.             System.out.printf("(%d,%d)%n" , currentRow, currentCol);
  114.  
  115.             int newParentRow = parent_row[currentRow][currentCol];
  116.             int newParentCol = parent_col[currentRow][currentCol];
  117.             if (newParentRow < 0 || newParentCol < 0) break;
  118.  
  119.             currentRow = newParentRow;
  120.             currentCol = newParentCol;
  121.  
  122.         }
  123.  
  124.         int weight = max_w - currentRow;
  125.         int value = best_val[max_w][v.length-1];
  126.  
  127.         System.out.println("\nWeight: " + weight);
  128.         System.out.println("Value: " + value);
  129.         System.out.println("the number of iterations : " + iterationCount);
  130.  
  131.         return value;
  132.     }
  133.  
  134.     private static void print2DArray(int[][] ary){
  135.         for (int i = 0; i < ary.length; i++) {
  136.             for (int j = 0; j < ary[i].length; j++) {
  137.                 System.out.printf("%3d" , ary[i][j]);
  138.             }
  139.             System.out.println();
  140.         }
  141.     }
  142. }
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.

×