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
    }
}

GitHub Link

BasicPractice_Snapsack.md

GitHub Gist: instantly share code, notes, and snippets.

Gist262588213843476