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.

# Snapsack Problem

Snapsack problem refers to the situation you want to find a combination of items that can fill up a container. Each items should be attached with a value, and there should be a target value that means a container is filled up. For example, a container has 25 spaces and there are items that will take 1, 5, 7, 6, 4 or 10 spaces. You have to find all the combinations that fit the container.

# Idea (In Python)

``````# stack: a stack that store the current combination
# items: available items, each item has a value
# available_space: the spaces left of the current combination
# index: the index of items it is going to match
function find_combinations_recursively(stack, items, available_space, index):
# check for invalid target or value
value = items[index]
if (target <= 0 or value <= 0): return
# combinations found!
if (target == value):
stack.push(value)
print_combinations(stack)
stack.pop(value)
return
# push the current value and found combination recursively with it
stack.push(value)
space_left = target - value
find_combinations_recursively(stack, items, space_left, index - 1)
stack.pop(value)
# finished matching current value, move to the next one
find_combinations_recursively(stack, items, target, index - 1)

# function to start the recursive matching function
function find_combinations(container, items):
# sorting is optional, but matching from the largest item
# will help speeding up the process
items.sort_values()
stack = new_stack()
available_space = container.size
index = items.last_index
find_combinations_recursively(stack, items, available_space, index)
``````

# Solution in Java

``````import java.util.*;

/**
* Created by nickwph on 10/18/15.
*/
public class BasicPractice_Snapsack {

private static Stack<Integer> mSnapsack = new Stack<>();

private static void printSnapsack() {
int total = 0;
for (int i = 0; i < mSnapsack.size(); i++) {
total += mSnapsack.get(i);
System.out.printf(String.valueOf(mSnapsack.get(i)));
System.out.printf((i < mSnapsack.size() - 1) ? " + " : " = " + total + "\n");
}
}

private static void findCombinations(List<Integer> list, int target, int position) {
if (target <= 0 || position < 0 || position >= list.size() || list.get(position) <= 0) {
// invalid target or position
return;
}
int value = list.get(position);
if (target == value) {
// solution found, print snapsack
mSnapsack.push(value);
printSnapsack();
mSnapsack.pop();
return;
}
// push the current value and found combination recursively
mSnapsack.push(value);
findCombinations(list, target - value, position - 1);
mSnapsack.pop();
// finished matching current value, move to the next one
findCombinations(list, target, position - 1);
}

private static void findCombinations(List<Integer> list, int target) {
// values must be small to large
Collections.sort(list);
findCombinations(list, target, list.size() - 1);
}

public static void main(String[] args) {
findCombinations(Arrays.asList(1, 5, 2, 2, 3, 7, 6, 4, 10), 27);
// 10 + 7 + 6 + 4 = 27
// 10 + 7 + 5 + 4 + 1 = 27
// 10 + 7 + 5 + 3 + 2 = 27
// 10 + 7 + 5 + 2 + 2 + 1 = 27
// 10 + 7 + 4 + 3 + 2 + 1 = 27
// 10 + 7 + 4 + 3 + 2 + 1 = 27
// 10 + 6 + 5 + 4 + 2 = 27
// 10 + 6 + 5 + 3 + 2 + 1 = 27
// 10 + 6 + 5 + 3 + 2 + 1 = 27
// 10 + 6 + 4 + 3 + 2 + 2 = 27
// 10 + 5 + 4 + 3 + 2 + 2 + 1 = 27
// 7 + 6 + 5 + 4 + 3 + 2 = 27
// 7 + 6 + 5 + 4 + 2 + 2 + 1 = 27
}
}
``````
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.