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方式：要么将所有项目权重相加，要么尝试对其进行更智能的计算。

Answer 2

您想要一个动态规划 (DP) 解决方案，而不是完全是背包问题。不过，背包有一个 DP 解决方案。

您的情况的解决方案是形成必要的重复。由于您的目标是最小化金钱，因此每个状态转换都将增加重量和项目编号以形成新状态。

所以，你的状态空间是：DP[Weight][Item]

编码留作练习。