Search code examples
pythonalgorithmoptimizationdynamic-programming

How to find minimum cost and combination that satisfies (or over) the goal?

I have an algorithm problem created by myself, and I am seeking some guidance here. The goal is to get at least X gold. There are different dealers selling different amounts of golds at different prices. I need to find an optimal combination that minimizes the cost while buying at least X gold.

Rules:

  • You must buy the gold in full amounts
  • You can buy any number of the same item

This resembles an unbounded knapsack problem, but in this problem there are no limit to the amount of gold to buy. Solving this using knapsack will give me solutions that are below the required amount of the goal, which are obviously wrong answers. Obviously I could brute-force it by gradually increasing the limit of the knapsack, but that would not be optimal in terms of performance.

As mentioned, I am seeking for some guidance here, on some less known algorithms that would solve this problem. I am not asking for code.

In an example, these are the prices available.

Item ID Gold Price
1 120 0.99
2 600 4.99
3 1,960 14.99
4 3,960 29.99
5 4,970 38.89
6 6,560 49.99
7 12,960 99.99
8 14,000 104.99

For this example, my task is to buy at least 12,880 gold. I need to find the combination and how many of each item I need to buy to satisfy the goal, which is get at least 12,880 gold while minimizing the cost.

My attempt to solve is the process of finding the algorithm to solve it. Here is a sheet with the different combinations I have tested, but I still cannot find a viable algorithm to find the optimal combination. Sheet showing my attempt to find the algorithm

In the image, you can see that buying 2 item_4 and 1 item_5 is currently my best solution. But it is not for certain the optimal solution.

Edit 1:

Add some more details/rules above

Edit 2:

I am just asking for some guidance here and not any code from you guys. I have solved similar problems with unbounded knapsack, but the solution cannot be applied here at all. This is because I need at least the amount, and not less than or equal to the amount. These are two different problems and I don't see any reason to post an unrelated code regarding the knapsack that does not even works as an attempt to solve the problem.

Edit 3:

I realized that I need to scope this question a bit, to make it reasonable. So here are the constraints.

n: Amount of gold in the goal
k: Number of dealers/items
m: Maximum amount of gold that will be sold as a single purchase

n <= 1000000
k <= 1000
m <= 10000000

I am again not looking for any code from you, just some advice for possible solutions, and I will write my own code.

Solution

  • To solve the problem, we need to extend the generic unbounded knapsack algorithm for minimizing cost with additional steps. Here I present a generic solution for all unbounded knapsack problems with at least W weight while minimizing total cost.

    Preconditions:

    • It is assumed that non-integer numbers have a limited number of decimal places. To work with integers, these numbers are multiplied by a factor. For example, 49.99 becomes 4999.
    • The terms "gold" and "price" are used interchangeably with "weight" and "cost," respectively, to align with the knapsack algorithm terminology.
    • Let W represents the required weight.
    • Let N be the number of items.

    Solution:

    1. Apply the general algorithm for solving the unbounded knapsack problem (minimizing cost) to construct a dp table. The dp table contains minimized costs and maximized weights for all capacities up to the required weight W. Additionally, maintain an array to store the combination of items for later retrieval.
    2. Assuming the dp table is sorted in ascending order based on capacity, follow these steps:
      • Initialize min_cost as infinity.
      • Iterate over each item in the items list and calculate the difference W - item_weight. For each iteration, search the dp table to find the first maximized weight that is equal to or greater than the calculated value. Use binary search for this.
      • As a result, the sum of found_weight and item_weight represents a total weight of at least W.
      • Use the index of the found weight in the dp_costs array to calculate the total cost.
      • If the total cost is less than the current min_cost, update both min_cost with the new value.
      • After completing the item loop, use the found_weight and item weights to find the combination of needed to achieve the min_cost.

    Complexity:

    Time: O(N * (W + log(W)))

    First Knapsack with O(N * W), then binary search within a loop O(N log(W))

    Space: O(W)

    We are using 1D lists for the "dp table".

    Final Code:

    # Items with weights and costs
items = [
    (120, 99),
    (600, 499),
    (1960, 1499),
    (3960, 2999),
    (4960, 3889),
    (6560, 4999),
    (12960, 9999),
    (14000, 10499),
]

def find_index_of_first_occurrence_or_higher(lst, value):
    ''' Binary search on a sorted list and returns the index of the first occurrence of a value or the next higher value if the value is not found.'''
    lo, hi = 0, len(lst) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if lst[mid] < value:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi + 1

def unbounded_knapsack_minimize_cost_required_capacity(items, capacity):
    dp_costs = [float('inf')] * (capacity + 1)      # Accumulated costs
    dp_wts = [0] * (capacity + 1)                   # Accumulated weights
    dp_items = [0] * (capacity + 1)                 # Item IDs in sequence
    dp_costs[0] = 0
    
    # Iterate over each capacity from 1 to the maximum capacity
    for i in range(1, capacity + 1):
        for j, (wt, cost) in enumerate(items):
            # Check if the weight of the current item is less than or equal to the current capacity
            if wt <= i:
                dp_wt = dp_wts[i - wt] + wt
                # If adding the item gives more weight than previously
                if dp_wt >= dp_wts[i]:
                    dp_cost = dp_costs[i - wt] + cost
                    # If the accumulated cost is less than previously
                    if dp_cost < dp_costs[i]:
                        dp_costs[i] = dp_cost
                        dp_wts[i] = dp_wt
                        dp_items[i] = j
        if dp_wts[i] == 0:
            # Use previous best as current best
            dp_costs[i] = dp_costs[i-1]
            dp_wts[i] = dp_wts[i-1]
            dp_items[i] = dp_items[i-1]
    
    # There could be items that gives more weight but less total cost. To handle these cases, loop through all the items once
    # Make use of the already created dp (i.e dp_costs) table, remove equivalent amount or less from the accumulated weight. Then apply the item weight and check if the cost is less.
    min_cost = float('inf')
    for i, (wt, cost) in enumerate(items):
        weight_to_find = max(capacity - wt, 0)
        
        found_weight = find_index_of_first_occurrence_or_higher(dp_wts, weight_to_find)
        dp_cost = dp_costs[found_weight] + cost
        
        if dp_cost < min_cost:
            min_cost = dp_cost
            min_cost_last_item = i
            total_weight = found_weight
    
    # Find the total combination that gives the min_cost
    min_combination = [min_cost_last_item]
    while total_weight > 0:
        item = dp_items[total_weight]
        min_combination.append(item)
        # Find previous item by subtracting weights
        item_weight = items[item][0]
        total_weight -= item_weight
    return min_cost, min_combination

capacity = int(input("Input capacity of the knapsack: "))
min_cost, min_combination = unbounded_knapsack_minimize_cost_required_capacity(items, capacity)

print("Minimum cost:", min_cost/100)
print("Minimum combination:", min_combination)
print("Final weight:", sum(map(lambda x: items[x][0], min_combination)))