You've successfully subscribed to Nicholas Workshop
Welcome back! You've successfully signed in.
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.