Binary Optimization is particularly useful for the multiple knapsack problem.
When an item has a selection limit s, meaning it can be chosen at most s times, the traditional approach requires O(n * s * m) time complexity. However, using binary optimization, the complexity can be reduced to O(n * log(s) * m)
The core idea of binary optimization is:
- Decomposing s into a binary representation. For example, if s = 13, it can be split into 1, 2, 4, 6.
- 2^0 = 1
- 2^1 = 2
- 2^2 = 4
- 13 – 1 – 2 – 4 = 6
- This way, we only need to consider log(s) new items instead of s items.
- Each decomposed item has its weight and value multiplied by the corresponding factor k from the decomposition.
Example:
Problem Description
You have N types of items and a knapsack with a capacity of V.
For each i-th type of item, you can have at most s_i pieces, each with a volume of v_i and a value of w_i.
The task is to determine which items should be placed into the knapsack to maximize the total value, while ensuring that the total volume of the items does not exceed the knapsack’s capacity.
You need to output the maximum total value.
Input Format
The first line contains two integers N and V, separated by a space, representing the number of item types and the knapsack’s capacity, respectively.
The next N lines each contain three integers v_i, w_i, and s_i, separated by spaces, representing the volume, value, and quantity of the i-th item.
Output Format
Output a single integer, which is the maximum total value.
Constraints
- 0 < N ≤ 1000
- 0 < V ≤ 2000
- 0 < v_i, w_i, s_i ≤ 2000
N, V = map(int, input().split())
Good = []
for _ in range(N):
weight, value, nums = map(int, input().split())
k = 1
while k <= nums:
nums -= k
Good.append((weight * k, value * k))
k *= 2
if nums > 0:
Good.append((weight * nums, value * nums))
dp = [0] * (V + 1)
for w, v in Good:
for j in range(V, w - 1, -1):
dp[j] = max(dp[j], dp[j - w] + v)
print(dp[V])