DEV Community

Leo
Leo

Posted on

A Knapsack related problem

The knapsack problem is a combinational problem: given a set of items with different weights and values, how can you put them in a knapsack of an X capacity and get the highest value?

Knapsack problem

This problem is one of the problems that you learn at university, or the simple code of the ATM machine when you need to create an algorithm that calculate the amount of bills to deliver to customer.

One simple code

One basic way to solve this is using a loop to insert items from the highest value to the lowest value and exit when the limit is reached

public class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("amount to draw: ");
        int input;
        if (!int.TryParse(Console.ReadLine(), out input))
        {
            throw new Exception("invalid input");
        }

        int[] availableBills = new int[]
        {
            100, 50, 10, 5, 2, 1
        };
        int[] result = new int[availableBills.Length];

        int currentAmount = 0;
        while (currentAmount < input)
        {
            int remaining = input - currentAmount;
            // get the highest value under difference

            int index = -1;
            int amountOfNextBill = 0;
            for (int x = 0; x < availableBills.Length; x++)
            {
                if (availableBills[x] <= remaining)
                {
                    index = x;
                    amountOfNextBill = (int)Math.Floor(remaining / (double)availableBills[x]);
                    break;
                }
            }

            if (index == -1)
            {
                throw new Exception($"cannot find a bill for value: {remaining}");
            }

            currentAmount += amountOfNextBill * availableBills[index];
            result[index] += amountOfNextBill;
        }

        // output the result
        Console.WriteLine("\nResult:");
        for (int i = 0; i < result.Length; i++)
        {
            Console.WriteLine($"{result[i]} of $ {availableBills[i]}");
        }

        return;
    }
}
Enter fullscreen mode Exit fullscreen mode

running this program with 267 (example) will give the output:

amount to draw:
267

Result:
2 of $ 100
1 of $ 50
1 of $ 10
1 of $ 5
1 of $ 2
0 of $ 1
Enter fullscreen mode Exit fullscreen mode

The problem

The main problem with this approach is the need for the $ 1 bill. What happens if we don't have the bill of $ 1? If you try to draw $ 3 you just can't because the possible values are 2, 4, 6 and so on.

Another problem is the set of combinations, if you test this code with available bills of 100, 50 and 30 and an input of 160 you get the exception: cannot find a bill for value: 10. In this version of the code the loop will get first one bill of 100 and then one bill of 50 because this combination will fit bellow $ 160 mark (100 + 50 -> 150), so the remaining is 10, but you don't have that bill.

There is a combination that solves this input, which is one bill of 100 plus 2 bills of 30, but the algorithm needs to skip the 50 value. Also, this problem cannot be solved with a simple additional loop that sums the next bill because there are deep set of combinations when you have more grained set of available bills.

The Approach

There are codes that are CPU bound and others are memory bound. For knapsack related problems there are algorithms which can solve with less time, but wich the best combination and others that maybe can't solve the problem because there is no time available but gives the best combination.

So, if there are a deep set of combinations and one of them can solve the problem we can create a code that reproduces all of them, and here we are looking for a very hungry CPU/memory algorithm.

Starting from the lowest bill, create combinations with the same bill, but without crossing the limit of input (160 in this case):

example: available bills of 30, 50, 100

30 -> 30, 60, 90, 120, 150
50 -> 50, 100, 150
100 -> 100
Enter fullscreen mode Exit fullscreen mode

now, let's flat map it and order by the result value, you need to store the source to backtrack the bills after:

1x30 -> 30
1x50 -> 50
2x30 -> 60
3x30 -> 90
1x100 -> 100
2x50 -> 100
4x30 -> 120
3x50 -> 150
5x30 -> 150
Enter fullscreen mode Exit fullscreen mode

When the result values are equivalent (example: 2x50 equals 1x100) you can opt to discard the most complicated one (which have the most amount of bills).

for each item of these sets, starting from the lower, combine it with all of the items ahead and store in the list again:

example:

1x30 + 1x50 -> 80
Enter fullscreen mode Exit fullscreen mode

but discard when you find an equivalent value wich less amount of bills, example:

1x30 + 2x30 == 3x30
2x50 == 1x100
Enter fullscreen mode Exit fullscreen mode

You will end up with a list of all possible combinations under 160, and you will find the combination that solves the problem when you hit the combination of 2x30 + 1x100 -> 160:

1x30 -> 30
1x50 -> 50
1x30 + 1x50 -> 80
2x30 -> 60
3x30 -> 90
1x100 -> 100
2x50 -> 100
1x50 + 2x30 -> 110
4x30 -> 120
1x30 + 1x100 -> 130
1x50 + 3x30 -> 140
3x50 -> 150
5x30 -> 150
2x30 + 1x100 -> 160
Enter fullscreen mode Exit fullscreen mode

What I have learnt from this code

After deploying this code I found it very robust, giving solution that we looking at first place can't believe that was possible to solve. Also, this code can be very slow under some combinations

So, if you have the 1 $ bill available, go with the basic algorithm and use this for a backup solution.

The code

I uploaded the code to github at https://github.com/lbosquett/knapsack, it uses weight and values but the main concept is the same of this article

Top comments (0)