作业帮这个动态规划算法问题怎么解决啊?Recall the greedy algorithm for Knapsack from the notes.Show that, for every constant c < 2, there is an instance of Knapsackfor which the greedy algorithm produces a solution that is greater thanc times
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/25 01:43:24
这个动态规划算法问题怎么解决啊?Recall the greedy algorithm for Knapsack from the notes.Show that, for every constant c < 2, there is an instance of Knapsackfor which the greedy algorithm produces a solution that is greater thanc times
这个动态规划算法问题怎么解决啊?
Recall the greedy algorithm for Knapsack from the notes.
Show that, for every constant c < 2, there is an instance of Knapsack
for which the greedy algorithm produces a solution that is greater than
c times optimal. (Hint: recall the example given in class with capacity
19 with three items: u
1
with weight 11 and value 11.1, one with weight
10 and value 10, and one with weight 9 and value 9. In this case, the
optimal solution has value 19, whereas the greedy solution provides a
solution of value 11.1.)
这个动态规划算法问题怎么解决啊?Recall the greedy algorithm for Knapsack from the notes.Show that, for every constant c < 2, there is an instance of Knapsackfor which the greedy algorithm produces a solution that is greater thanc times
贪婪算法和动态规划有所不同,可以百度下贪婪算法,找下思路