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!