algorithmcombinationsdynamic-programming

Reputation: 674

Number of all combinations in Knapsack task

There is a classic Knapsack problem. My version of this problem is a little different.

Given set of items, each with a mass, determine the number of combinations to pack items so that the total weight is less than or equal to a given limit.

For example, there is 5 items with mass: 1, 1, 3, 4, 5. There is a bug with limit = 7. There are the following combinations:

Is there a way to count number of combinations without brute?

Upvotes: 5

Answers (4)

Ragin P M

Reputation: 1

This algorithm uses BFS to generate all possible combinations. Before execution, ensure the items in the list are sorted. At each BFS level, duplicate combinations are checked. If the level increments, items in the HashSet used for duplicate checking are cleared. For scenarios involving a large number of items and high limits, this approach is expected to reduce execution time compared to a recursive algorithm. And memory usage is lesser because, at starting of each new level the HashSet used for duplicate checking will be cleared. The 'minValueOfItems' is the minimum value inside the items List.

public void getCombination(List<Integer> items, double minValueOfItems, double limit, int size){

    HashSet<String> resultStringSet = new HashSet<>();
    HashSet<String> visitedStringSet = new HashSet<>();
    Queue<String> combinationStack = new LinkedList<>();
    Queue<Integer> positionOfItemsStack = new LinkedList<>();
    Queue<Double> totalQuantityStack = new LinkedList<>();
    combinationStack.add(" ");
    positionOfItemsStack.add(0);
    totalQuantityStack.add((double)0);
    int previousPosition = -1;
    while(!combinationStack.isEmpty()){
        String topCombination = combinationStack.peek();
        int position = positionOfItemsStack.peek();
        double currentSumQuantity = totalQuantityStack.peek();
        combinationStack.poll();
        positionOfItemsStack.poll();
        totalQuantityStack.poll();
        if(limit-currentSumQuantity<minValueOfItems){
            if(!resultStringSet.contains(topCombination)){
                resultStringSet.add(topCombination);
                System.out.println(topCombination);
            }
        }
        if(position < size && currentSumQuantity + items.get(position) <= limit) {
            if(previousPosition!=position){
                visitedStringSet = new HashSet<>();
                previousPosition = position;
            }
            if (!visitedStringSet.contains(topCombination+String.valueOf(position))) {
                visitedStringSet.add(topCombination+String.valueOf(position));
                String newCombination = null;
                if (topCombination.equals(" ")) {
                    newCombination = String.valueOf(items.get(position)) + ",";
                } else {
                    newCombination = topCombination + String.valueOf(items.get(position)) + ",";
                }
                double newSum = currentSumQuantity + items.get(position);
                combinationStack.add(topCombination);
                combinationStack.add(newCombination);
                positionOfItemsStack.add(position + 1);
                positionOfItemsStack.add(position + 1);
                totalQuantityStack.add(currentSumQuantity);
                totalQuantityStack.add(newSum);
            }
        }
    }
}

Upvotes: 0

pjsofts

Reputation: 198

This is one solution:

items = [1,1,3,4,5]
knapsack = []
limit = 7

def print_solutions(current_item, knapsack, current_sum):
    #if all items have been processed print the solution and return:
    if current_item == len(items):
        print knapsack
        return

    #don't take the current item and go check others
    print_solutions(current_item + 1, list(knapsack), current_sum)

    #take the current item if the value doesn't exceed the limit
    if (current_sum + items[current_item] <= limit):
        knapsack.append(items[current_item])
        current_sum += items[current_item]
        #current item taken go check others
        print_solutions(current_item + 1, knapsack, current_sum )

print_solutions(0,knapsack,0)

prints:

[]
[5]
[4]
[3]
[3, 4]
[1]
[1, 5]
[1, 4]
[1, 3]
[1]
[1, 5]
[1, 4]
[1, 3]
[1, 1]
[1, 1, 5]
[1, 1, 4]
[1, 1, 3]

Upvotes: 4

Neithrik

Reputation: 2068

EACH ITEM USED UNLIMITED TIMES

This is rather straightforward extension of original problem.

As you probably know you use DP to solve original problem, where weight of items must be exactly W. When you finish with DP, you will also have solution for all weights < W. To get your solution simply sum up solutions for weights from 1 to W (and +1 for empty set).

EACH ITEM USED ONCE

In this case, there is not other way, but to brute-force all possible combinations. This problem is NP-hard and will have time complexity of O(2^n).

To brute-force use next code (borrowed from @pjsofts):

items = [1,1,3,4,5]
knapsack = []
limit = 7

def print_solutions(current_item, knapsack, current_sum):
    #if all items have been processed print the solution and return:
    if current_item == len(items):
        print knapsack
        return

    #don't take the current item and go check others
    print_solutions(current_item + 1, list(knapsack), current_sum)

    #take the current item if the value doesn't exceed the limit
    if (current_sum + items[current_item] <= limit):
        knapsack.append(items[current_item])
        current_sum += items[current_item]
        #current item taken go check others
        print_solutions(current_item + 1, knapsack, current_sum )

print_solutions(0,knapsack,0)

Upvotes: 3

Random Dev

Reputation: 52280

well as others posted some solutions too, here is a translation of the naive extension of the problem using Haskell and simple recursion:

combinations :: Int -> [Int] -> [[Int]]
combinations _ [] = [[]]
combinations w (x:xs)
  | w >= x = [ x:ys | ys <- combinations (w-x) xs] ++ combinations w xs
  | otherwise = combinations w xs

test-run

λ> combinations 7 [5,4,3,1,1]
[[5,1,1],[5,1],[5,1],[5],[4,3],[4,1,1],[4,1],[4,1],[4],[3,1,1],[3,1],[3,1],[3],[1,1],[1],[1],[]]

what's going on?

starting with 5 you have two choices: either you take it or not.

if you take it you have limit 2 left and so you should recursively look for how many ways you can do this
if not you still have limit 7 but only 1,1,3,4 to look for ....

the algorithm translates this into basic Haskell in a hopeful readable way - feel free to ask for details

remarks

I did not look at the performance at all - but it should be easy doing the same stuff you would do with the original problem (rewrite columns of the table, ...)