在我的示例中，7 英寸长杆可以分为 6 + 1 或 2 + 2 + 3 方式。现在假设我的算法是否选择第一个分区。
6 + 1
代替
2 + 2 + 3
我应该说这是一种半贪婪方法吗，据我所知，棒材切割问题是一个动态规划问题
user2375464
问问题
1802 次
2 回答
0
贪心算法
半贪婪方法
贪心算法是一些试图解决整个问题的算法，通过将其划分为子问题，并尝试在子问题的上下文中为这些问题选择最佳解决方案。这通常会导致解决方案，但不会导致全局最优解决方案。半贪婪没有任何意义。它要么是，要么不是。
棒材切割问题
棒材切割问题是切割棒材的最有效方法，它基于一个数值表，该表格告知切割棒材的成本。
你的算法，因为它是
好吧..我看不出贪婪的价值。如果我们试图将其拆分为尽可能少的数字，那么显然您会贪婪地选择小于要拆分的数字的最大数字。
贪心算法需要一些目标来实现。简单地分裂一根“棒”并没有隐含的价值。
如果我们有成本矩阵，您的算法
如果您有一个成本矩阵，并且您的算法试图使用最便宜的值进行削减，那么它将是一个贪心算法，因为您对成本很贪心。
于 2013-05-12T20:47:18.413 回答
0
没有像半贪心算法这样的术语，好吧。
它选择第一选择是因为它寻找更多的价格，如果它终止了，它不会去寻找另一个选择，这都是因为<=表达；它比较了棒切割组合的最优性，而不是因为它是一个半贪婪算法。
我相信你现在很清楚
于 2013-05-12T20:41:59.353 回答