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

Nicholas Wong
Nicholas Wong

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
    }
}
BasicPractice_Snapsack.md
GitHub Gist: instantly share code, notes, and snippets.
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.