zzxxyy518
zzxxyy518
2019-10-18 17:23
采纳率: 100%
浏览 426

分组背包的变式问题(每组物品必须选择一个不能不选)

有n组物品,必须从每一组物品中选出一个,在物品的总价值不超过一个给定值的情况下,得到最高的价值。

目前我用递归在每一次递归过程中设置了单独的循环查找每一类中的所有物品,后序问题要求用动态规划进行优化。

但是动态规划要求每个子问题具有最优解,但是对于这个问题对于子问题的最优解就可能会导致下一个问题无解,希望大神们给点思路

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • bobhuang
    bobhuang 2019-10-18 17:40
    已采纳

    把子问题理解为:“(组合价值, 组合物品列表)的列表”,从一组物品开始,逐步添加下一组物品,最终结果出来之后筛选符合条件“总价值不超过给定值”的组合价值最大的项。
    优化:在计算过程中,可以把组合价值超过给定值的项剔除。

    点赞 评论

相关推荐