Bounded Knapsack Problem — வரம்புள்ள முட்டைச் சாவி

k_i முறை வரம்பு — dp[i][w]; நகல் வளையம் அல்லது monotonic queue.

உண்மை உலகில் இது ஏன் முக்கியம்?

கிடங்கு — SKU வரம்பு. பட்ஜெட் — திட்ட வரம்பு.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

அடிப்படை மூன்று வளையம்; வேகம் — இரட்டைப்படுத்தி 0/1 knapsack.

Pythonில் முயற்சி செய்வோம்

def bounded_knapsack(weights: list[int], values: list[int], counts: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for wt, val, cnt in zip(weights, values, counts):
        for _ in range(cnt):
            for w in range(W, wt - 1, -1):
                dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]


print(bounded_knapsack([1, 2], [10, 20], [2, 1], 4))

அடிக்கடி நேரும் தவறுகள்

• unbounded என தவறாக.
• எடை நிரப்ப முடியாத நிலை.

முக்கியச் சுருக்கக் குறிப்புகள்

• எண்ணிக்கை இரட்டைப்படுத்தல்.
• சுழியம் மட்டும் சாத்தியம் சோதனை.