Knapsack Problem

Introduction

Hello, I’ve run into a well studied issue in the computer science industry called the Knapsack problem. Even though there is a lot of information on the Wikipedia article, I struggle to find the solution I’m looking for because this is a special case of the problem.


My Issue

I’m trying to achive a money drop system that drops the required amount of money In 20 notes, 10 notes, 5 notes and 1 coin. This may be hard to understand, so let me give you an example.


Example

You have $20, $10, $5 and $1 notes.

For the purpose of modeling this example, you have an unlimited amount of these notes.

You have been given $50.

What is the minimum amount of notes you need to create this amount?

Solution

To make $50, you need:

  • Two $20 notes
  • One $10 note

There is a solution in Python on the article but I’m struggling to convert it to Lua:

def _get_change_making_matrix(set_of_coins, r: int):
    m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)]
    for i in range(1, r + 1):
        m[0][i] = float('inf')  # By default there is no way of making change
    return m

def change_making(coins, n: int):
    """This function assumes that all coins are available infinitely.
    n is the number to obtain with the fewest coins.
    coins is a list or tuple with the available denominations.
    """
    m = _get_change_making_matrix(coins, n)
    for c, coin in enumerate(coins, 1):
        for r in range(1, n + 1):
            # Just use the coin
            if coin == r:
                m[c][r] = 1
            # coin cannot be included.
            # Use the previous solution for making r,
            # excluding coin
            elif coin > r:
                m[c][r] = m[c - 1][r]
            # coin can be used.
            # Decide which one of the following solutions is the best:
            # 1. Using the previous solution for making r (without using coin).
            # 2. Using the previous solution for making r - coin (without
            #      using coin) plus this 1 extra coin.
            else:
                m[c][r] = min(m[c - 1][r], 1 + m[c][r - coin])
    return m[-1][-1]

It’s a pretty complex piece of code that I don’t exactly understand.


Required Solution

Help on how to create a function that tackles this issue in Lua.


Any help on how to solve this issue will be appriciated!

1 Like

I’d say this would be easier for you to do:

function Separate(Amount)
	local Notes = {
		["Twenty"] = 0,
		["Ten"] = 0,
		["Five"] = 0,
		["One"] = 0
	}
	while Amount > 0 do
		if Amount % 20 == 0 then
			Notes["Twenty"] += 1
			Amount -= 20
		elseif Amount % 10 == 0 then
			Notes["Ten"] += 1
			Amount -= 10
		elseif Amount % 5 == 0 then
			Notes["Five"] += 1
			Amount -= 5
		else
			Notes["Ten"] += 1
			Amount -= 1
		end
	end
	return Notes["Twenty"], Notes["Ten"], Notes["Five"], Notes["One"]
end

local Amount = 0 --or whatever you want
local Notes_20,Notes_10,Notes_5,Notes_1 = Separate(Amount)
3 Likes

This Developer Hub article might be useful for you when you encounter similar problems in the future.

2 Likes

This code is a little bit spagetti code but I understood it and refactored it a bit. Here is the final working solution, with the help of @Administrat0r_J:

function Knapsack(Number, Denominations)
	assert(Number, "No number provided for the 'Knapsack' utility function.")
	assert(Denominations, "No denominations provided for the 'Knapsack' utility function.")
	
	local Required = {}
	
	table.sort(Denominations, function(A, B)
		if A > B then
			return true
		end
	end)
		
	while Number > 0 do
		for _, Denomination in ipairs(Denominations) do
			if Number % Denomination == 0 then
				table.insert(Required, Denomination)
				Number -= Denomination
				break
			end
		end
	end
	
	return Required
end

This was exactly what I was going to say. Well done.

1 Like