Nicholas Workshop

0/1 Knapsack Problem Dynamic Programming

Nicholas Wong -

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Drawing graph

int[] plot(int[] values, int[] weights, int numberOfItems, int capacity) {
	int[] map = int[numberOfItems, capacity];
	for (int j=0; j<capacity; j++) {
        map[0, j] = 0;  
    }
    for (int i=0; i<numberOfItems; i++) {
	    for (int j=0; j<capacity; j++) {
            if (j < w[i]) {
            	map[i, j] = map[i-1, j] // 1 up value
            } else {
				map[i, j] = max(
					map[i-1, j], // this value
					values[i] + map[i-1, j-wight[i, j]]) // this + 1 up level without weight
            }
        }
	}
	return map;
}

Find the content

Modify the program and memorize which items are picked

List<Integer> find(int[] values, int[] weights, int numberOfItems, int capacity) {
    boolean[][] keep = boolean[numberOfItems][capacity];
	int[][] map = int[numberOfItems][capacity];
	for (int j=0; j<capacity; j++) {
        map[0, j] = 0;  
    }
    for (int i=0; i<numberOfItems; i++) {
	    for (int j=0; j<capacity; j++) {
            if (j < w[i]) {
            	map[i, j] = map[i-1, j] // 1 up value
    	 		keep[i, j] = false
            } else {
    			int oneUpValue = map[i-1, j]; // 1 up value
				int thisValue = values[i] + map[i-1, j-wight[i, j]]) // this + 1 up level without weight
    			map[i, j] = max(oneUpValue, thisValue);
    			if (oneUpValue > thisValue) {
    				keep[i, j] = false;
    			} else {
    				keep[i, j] = true;
    			}
            }
        }
	}
    List<Integer> result = ArrayList<>()
    int weightLeft = capacity
    for (int i=numberOfItems-1, i>=0; i--) {
    	if (keep[i, weightLeft] == true) {
    		result.add(i);
    		weightLeft =- wights[i];
    	}
    	if (weightLeft<=0) {
            break;
        }
    }
	return result;
}

Reference