You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

0/1 Knapsack Problem Dynamic Programming

Nicholas Wong
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

Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.