Practice/Google/Knapsack Problem Variations

Knapsack Problem Variations

CodingMust

Problem

You are given a knapsack with a specific weight capacity and a collection of items. Each item has a weight and a value. The value of each item is constrained to be either 1 or 2 (no other values are possible). Additionally, weights may be decimal numbers with up to two decimal places.

Your task is to determine the maximum total value you can achieve by selecting items to place in the knapsack without exceeding its capacity. Each item can be selected at most once (this is a 0/1 knapsack variant).

Requirements

1. Implement a function that takes the knapsack capacity, a list of item weights, and a list of corresponding item values
2. Return the maximum total value achievable without exceeding the capacity
3. Handle decimal weights correctly (weights can have up to 2 decimal places)
4. All values are guaranteed to be either 1 or 2
5. Items cannot be partially selected

Constraints

• 1 ≤ number of items ≤ 1000
• 0 ≤ capacity ≤ 10000
• 0 < weight of each item ≤ capacity
• Each value is either 1 or 2
• Weights may be integers or decimals with up to 2 decimal places
• Expected time complexity: O(n × C) where n is the number of items and C is related to capacity
• Expected space complexity: O(C)

Examples

Example 1:

Input: capacity = 10 weights = [2, 3, 4, 5] values = [1, 2, 1, 2] Output: 5 Explanation: Select items at indices 0, 1, and 3 with total weight 2+3+5=10 and total value 1+2+2=5

Example 2:

Input: capacity = 7.5 weights = [2.5, 3.25, 4.0, 1.5] values = [2, 1, 2, 1] Output: 5 Explanation: Select items at indices 0, 2, and 3 with total weight 2.5+4.0+1.5=8.0. This exceeds capacity. Instead, select indices 0 and 2 with weight 2.5+4.0=6.5 and value 2+2=4. Or select 0 and 1 with weight 2.5+3.25=5.75 and value 2+1=3. Or 0, 1, 3 with weight 2.5+3.25+1.5=7.25 and value 2+1+1=4. Actually 0 and 2 give value 4, which seems best within capacity.

Example 3:

Input: capacity = 5 weights = [6, 7, 3] values = [2, 2, 1] Output: 1 Explanation: Only the item with weight 3 fits, giving a maximum value of 1