Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.awt.*;
- public class DP_Knapsack_Norepetition_CountWeight_Assignment {
- public static void main(String[] args) {
- int w[] = new int[]{1, 4, 6, 2, 5, 10, 8, 3, 9, 1, 4, 2, 5, 8, 9, 1};
- int v[] = new int[]{ 10, 5, 30, 8, 12, 30, 50, 10, 2, 10, 40, 80, 100, 25, 10, 5 };
- int max_w = 20;
- // int w[] = new int[]{6,3,4,2};
- // int v[] = new int[]{30,14,16,9};
- //
- // int max_w = 10;
- // int w[] = new int[]{11,11,11,2};
- // int v[] = new int[]{30,14,16,9};
- //
- // int max_w = 10;
- dp_knapsack_repitition(w, v, max_w);
- System.out.println();
- }
- private static int dp_knapsack_repitition(int[] w, int[] v, int max_w) {
- int best_val[][] = new int[max_w + 1][v.length]; // attention: we intend to allow from 0 ~ 10 (11 numbers instead of 10 numbres)
- int parent_row[][] = new int[max_w + 1][v.length];
- int parent_col[][] = new int[max_w + 1][v.length];
- int iterationCount = 0;
- // initialize the array
- for (int i = 0; i <= max_w; i++) {
- for (int j = 0; j < best_val[i].length; j++) {
- best_val[i][j] = -1;
- }
- }
- // set the base state -> w = 0
- for (int itemIndex = 0; itemIndex < v.length; itemIndex++) {
- best_val[0][itemIndex] = 0;
- parent_row[0][itemIndex] = -1; // no parent for the base case
- parent_col[0][itemIndex] = -1; // no parent for the base case
- }
- // set the base state -> v = 0 (no item is picked)
- for (int wIndex = 0; wIndex < max_w + 1; wIndex++) {
- best_val[wIndex][0] = 0;
- parent_row[wIndex][0] = -1; // no parent for the base case
- parent_col[wIndex][0] = -1; // no parent for the base case
- }
- System.out.println("\r\nbase state: ");
- print2DArray(best_val);
- for (int nowW = 1; nowW < best_val.length; nowW++) {
- for (int itemIndex = 0; itemIndex < w.length; itemIndex++) { // go through each item to try
- // increment iteraiton count
- iterationCount++;
- // find the best val
- int tmpVal = 0;
- if (w[itemIndex] <= nowW && itemIndex == 0) { // if this is the first item and it is ok to take
- tmpVal = Math.max( 0, v[itemIndex]);
- parent_row[nowW][itemIndex] = nowW - w[itemIndex]; // attention: if picked, the affordable weight will go down
- parent_col[nowW][itemIndex] = itemIndex;
- }else if (w[itemIndex] <= nowW && itemIndex != 0) { // if this is not the first item, then we decide whether to pick this one or not
- // get the better one
- int noPick = best_val[nowW][itemIndex - 1];
- int pick = v[itemIndex] + best_val[nowW - w[itemIndex]][itemIndex - 1];
- if (noPick > pick){
- parent_row[nowW][itemIndex] = nowW;
- parent_col[nowW][itemIndex] = itemIndex - 1;
- } else {
- parent_row[nowW][itemIndex] = nowW - w[itemIndex]; // attention: if picked, the affordable weight will go down
- parent_col[nowW][itemIndex] = itemIndex - 1;
- }
- tmpVal = Math.max(noPick, pick); // we either pick the current item or not
- }else if (w[itemIndex] > nowW && itemIndex != 0) {
- tmpVal = best_val[nowW][itemIndex-1]; // if too heavy, then try the previous item for this weight limit
- parent_row[nowW][itemIndex] = nowW;
- parent_col[nowW][itemIndex] = itemIndex - 1;
- }
- best_val[nowW][itemIndex] = tmpVal;
- } // end of inner for // 真正有意義的是當每一輪都到了最後一個item時,我們才知道在某個限重下,最好的組合是怎樣。(中間都只是輔助資訊)
- } // end of outer for
- System.out.println("\nfinal state: ");
- print2DArray(best_val);
- // System.out.println("final row: ");
- // print2DArray(parent_row);
- //
- // System.out.println("final col: ");
- // print2DArray(parent_col);
- // print parent
- System.out.println("\nThe final route: ");
- int currentRow = max_w;
- int currentCol = v.length-1;
- while(true){
- System.out.printf("(%d,%d)%n" , currentRow, currentCol);
- int newParentRow = parent_row[currentRow][currentCol];
- int newParentCol = parent_col[currentRow][currentCol];
- if (newParentRow < 0 || newParentCol < 0) break;
- currentRow = newParentRow;
- currentCol = newParentCol;
- }
- int weight = max_w - currentRow;
- int value = best_val[max_w][v.length-1];
- System.out.println("\nWeight: " + weight);
- System.out.println("Value: " + value);
- System.out.println("the number of iterations : " + iterationCount);
- return value;
- }
- private static void print2DArray(int[][] ary){
- for (int i = 0; i < ary.length; i++) {
- for (int j = 0; j < ary[i].length; j++) {
- System.out.printf("%3d" , ary[i][j]);
- }
- System.out.println();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement