KnapsackProblem.java

/*
	Given an array of items. The array consists of 
	multiple sub-arrays holding two int values, 
	representing the value and the weight of an item, 
	respectively. We are also given the maximum 
	capacity of a knapsack. 
	In light of the above, this implementation demonstrates
	how to solve the famous knapsack problem, where the aim
	is to fit items in the knapsack with a view to 
	maximizing their combined value. 

	Let c be the capacity of the knapsack and
	n be the number of items.
	Time complexity: O(nc) 
	Space complexity: O(nc)
*/
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class KnapsackProblem {

	public static void main(String[] args) {
		// An array of 4 items. Each subarray holds two
		// ints representing value and weight of an item.
		int[][] items = { { 1, 2 }, { 4, 3 }, { 5, 6 }, { 6, 7 } };
		// Max capacity of knapsack
		int capacity = 10;
		List<List<Integer>> result = knapsackProblem(items, capacity);
		// Selected items are: [4, 3] at idx 1 and [6, 7] at idx 3
		System.out.println(result); // [[10], [3, 1]]
	}

	public static List<List<Integer>> knapsackProblem(int[][] items, int capacity) {
		final int ITEMS = items.length;
		// Rows represent the items
		// Columns are the different capacity values.
		int[][] values = new int[ITEMS + 1][capacity + 1];

		int weight, value;
		// Problem is solved through dynamic programming
		for (int item = 1; item <= ITEMS; item++) {
			value = items[item - 1][0];
			weight = items[item - 1][1];
			for (int c = 0; c <= capacity; c++) {
				// If current item does not fit, then value is same
				// as the one with the previous item in knapsack
				if (weight > c) {
					values[item][c] = values[item - 1][c];
				} else {
					// Either you add current item or you don't
					values[item][c] = Math.max(values[item - 1][c], values[item - 1][c - weight] + value);
				}
			}
		}

		List<Integer> totalValue = Arrays.asList(values[ITEMS][capacity]);
		int item = ITEMS, c = capacity;
		List<Integer> finalItems = new ArrayList<>();
		// Package items added to knapsack into
		// final items list
		while (item > 0 && c > 0) {
			if (values[item][c] > values[item - 1][c]) {
				c -= items[item - 1][1];
				finalItems.add(item - 1);
			}
			item--;
		}

		List<List<Integer>> result = new ArrayList<List<Integer>>();
		result.add(totalValue);
		result.add(finalItems);
		return result;
	}
}