mellon销售农民的一种算法
mellon销售农民的一种算法
提问于 2013-07-17 14:06:45
我在网上看到的问题:一个卖瓜的农民有n个瓜。每个甜瓜的重量，一个整数(磅)，是不同的。一位顾客要了整整一百万磅未切好的西瓜。现在，农夫有以下问题:如果有可能满足客户，他应该通过尽可能有效地找到合适的瓜来做到这一点，否则就告诉客户不可能满足他的要求。
注意:这不是家庭作业，顺便说一下，我只是需要指导。
我的回答是:这似乎类似于硬币兑换问题(背包)和子集问题(回溯)。硬币更换:我可以将权重放入一个集合w= {5，8，3，2，...}，然后求解，子集问题也是如此。
所以基本上我可以使用任何一种方法来解决这个问题？
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-07-17 14:50:02
这正是一个整数背包问题，其中的解决方案没有浪费。有一个很好的动态编程/记忆策略可以帮助你解决这个问题。请参阅以下任一链接：
http://www.cs.ship.edu/~tbriggs/dynamic/
https://en.wikipedia.org/wiki/Knapsack_problem
实际上，子集和问题是0/1背包问题，其中权重等于每个项目的值。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17692288
复制相关文章
相似问题
腾讯云开发者
