c++ - 如何在这个算法难题中应用背包方法？

Question

假设您有一个项目列表及其 Weights[] 和 Price[] 。 现在给定两个整数 N<=100 和 K<=100 你必须找到你应该花费的最小金额使得你购买的元素的总重量恰好等于 K 并且元素数量不超过 N 并且如果不可能满足给定条件只打印 IMPOSSIBLE 。 您可以多次购买每件商品。

请告诉我如何在这个问题中应用背包，如果它不是背包问题那么如何解决它？

Answer 1

dp[i] = minimum money you have to pay to get weight i

dp[_] = infinity

for i = 1 to N do
  for j = item[i].weight to MaxWeight do
    dp[j] = min(dp[j], dp[j - item[i].weight] + item[i].price)

如果dp[K] != infinity，那就是你的解，否则无解。实际效率取决于您计算 MaxWeight 的方式:要么对所有项目权重求和，要么尝试更聪明。