0-1背包算法变种：可重复选取物品的背包问题求解问询

Hey there! When the 0-1 knapsack problem allows items to be selected multiple times, this is formally called the Unbounded Knapsack Problem—the key difference from 0-1 knapsack is that each item has no selection limit (you can take it 0, 1, 2, ... times as long as the total weight doesn't exceed the backpack's capacity). Let's break down how to solve it, using your specific example.

Core Solution Approach: Dynamic Programming #

The standard way to solve this problem is with dynamic programming (DP), which builds up the optimal solution incrementally. Here's the step-by-step logic:

1. State Definition #

Define dp[j] as the maximum total value we can get with a backpack capacity of j (where j ranges from 0 to the maximum capacity, 10 in your example).

2. State Transition Equation #

For each item (with weight w and value v), we iterate through the backpack capacities from w to the maximum capacity. The transition is:

dp[j] = max(dp[j], dp[j - w] + v)

Unlike the 0-1 knapsack (where we iterate capacities in reverse to avoid reusing items), we iterate forward here—this allows us to select the same item multiple times, since we're updating the dp array with the latest (already possibly including the current item) values.

3. Initialization #

• Set dp[0] = 0 (zero capacity means zero value)
• Initialize all other dp[j] values to 0 (since all item values are positive, starting at 0 works for this scenario)

Example Walkthrough #

Let's apply this to your problem:

• Items: Weight = [6, 5, 4, 2, 1], Value = [6.59, 6.49, 6.39, 6.29, 6.16]
• Max capacity: 10

First, let's calculate the value per unit weight for each item to get an intuition:

• Weight 6: ~1.098 per unit
• Weight 5: ~1.298 per unit
• Weight 4: ~1.597 per unit
• Weight 2: ~3.145 per unit
• Weight 1: 6.16 per unit (highest by far)

Intuitively, since the weight-1 item has the highest value per unit weight, filling the backpack entirely with this item will give the maximum value: 10 * 6.16 = 61.6. Let's confirm with the DP approach:

1. Initialize dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (indices 0-10)
2. Process the weight-1, value-6.16 item first:
   • For j from 1 to 10:
     dp[j] = max(dp[j], dp[j-1] + 6.16)
   • After this, dp[j] = 6.16 * j for all j.
3. Processing other items won't change the dp array, since adding any other item would result in a lower total value than using the weight-1 item. For example:
   • For j=10, using two weight-5 items gives 6.49*2=12.98, which is way less than 61.6.
   • Using five weight-2 items gives 6.29*5=31.45, still less than 61.6.

So the optimal solution is to select 10 copies of the weight-1 item, with a total value of 61.6.

Recommended Resources #

• 《背包问题九讲》: A classic Chinese-language resource that covers all knapsack variants (unbounded, 0-1, multi-dimensional, etc.) with detailed explanations and examples.
• 《Introduction to Algorithms》: The chapter on dynamic programming includes a section on the unbounded knapsack problem, explaining the underlying theory and proof of optimality.
• University algorithm courses: Most introductory algorithm courses cover dynamic programming and the unbounded knapsack problem as a core example, walking through both theory and practice.

内容的提问来源于stack exchange，提问作者Priytosh Tripathi