Knapsack budgetting

Question

The problem

I have $1000 of money. With it I can buy 3 items:

• Item 1 which costs 45 dollars.
• Item 2 which costs 75 dollars.
• Item 3 which costs 25 dollars.

I want to know the optimal amount of each item to buy to come as close as possible to the following statements :

• 75% of the money I spend has been allocated to Item 1

• 20% of the money I spend has been allocated to Item 2

• 5% of the money I spend has been allocated to Item 3

There is one strong rule: As long as there is enough money left to buy one of the items, I have to continue buying.

Example :

What I mean with 'as close as possible to the following statements'

Solution 1:

• 80% Item 1

• 20% Item 2

• 0% Item 3

sum of percentage differences = (80-75) + (20-20) + (5-0) = 10%

Solution 2:

• 90% Item 1
• 5% Item 2
• 5% Item 3

sum of percentage differences = (90-75) + (20-5) + (5-5) = 30%

The better solution is Solution 1 (because 10% is a smaller percentage difference than 30%)

Answer 1

If you only bought Item 1, then you could buy $\lfloor \frac{1000}{45} \rfloor = 22$ of them. Similarly, you could buy at most $\lfloor \frac{1000}{75} \rfloor = 13$ of Item 2, or $\lfloor \frac{1000}{25} \rfloor = 40$ of Item 3. This gives us a maximum search space of $23 \times 14 \times 41 = 13202$ combinations (adding 1 to each factor because 0 is a valid quantity), amenable to brute-force search by computer. So let's just do that.

ITEM1_PRICE = 45
ITEM2_PRICE = 75
ITEM3_PRICE = 25
MAX_TOTAL_PRICE = 1000
MIN_TOTAL_PRICE = MAX_TOTAL_PRICE - min(ITEM1_PRICE, ITEM2_PRICE, ITEM3_PRICE)
ITEM1_BUDGET_PROP = 0.75
ITEM2_BUDGET_PROP = 0.20
ITEM3_BUDGET_PROP = 0.05

# Store solutions in a list in case there's a tie
best_solutions = []
best_error = float('inf')

for qty1 in range(MAX_TOTAL_PRICE // ITEM1_PRICE + 1):
    for qty2 in range(MAX_TOTAL_PRICE // ITEM2_PRICE + 1):
        for qty3 in range(MAX_TOTAL_PRICE // ITEM3_PRICE + 1):
            price1 = qty1 * ITEM1_PRICE
            price2 = qty2 * ITEM2_PRICE
            price3 = qty3 * ITEM3_PRICE
            total_price = price1 + price2 + price3
            if MIN_TOTAL_PRICE <= total_price <= MAX_TOTAL_PRICE:
                prop1 = price1 / MAX_TOTAL_PRICE
                prop2 = price2 / MAX_TOTAL_PRICE
                prop3 = price3 / MAX_TOTAL_PRICE
                error = abs(prop1 - ITEM1_BUDGET_PROP) + abs(prop2 - ITEM2_BUDGET_PROP) + abs(prop3 - ITEM3_BUDGET_PROP)
                if error < best_error:
                    best_solutions = [(qty1, qty2, qty3)]
                    best_error = error
                elif error == best_error:
                    best_solutions.append((qty1, qty2, qty3))

print(best_solutions)

Running the program shows a unique optimal solution of $(16, 3, 2)$, i.e.:

• 16 units of Item 1 @ \$45, for a total price of \$720 (versus ideal \$750).
• 3 units of Item 2 @ \$75, for a total price of \$225 (versus ideal \$200).
• 2 units of Item 3 @ \$25, for a total price of \$50 (exactly the ideal amount).
• \$5 left over that's too small to buy anything with.