背包问题优化2的代码似乎有个bug？

来源：9-6 0-1背包问题的优化和变种

想不出来叫什么

2018-05-21

老师您好，以下是背包问题优化2的核心部分：

for(int i = 1 ; i < n ; i ++)    
    for(int j = C ; j >= w[i] ; j --)    
        memo[j] = Math.max(memo[j], v[i] + memo[j - w[i]]);

这里似乎有一个bug: 第二重循环中，当j < w[i]时就停止，似乎要求物品的重量在w数组中必须按升序排列，如果是乱序的话，这段代码可能会导致结果出错。

如果我的看法正确的话，若给出的w数组是乱序的，就必须对其进行排序，总的时间复杂度就变成了O(nlogn + n*c)，时间复杂度似乎变长了。

您看我说的对吗？谢谢老师！

写回答

1回答

liuyubobobo

2018-05-21

已采纳

不需要排序。背包问题的解题逻辑中和物品的重量是否有序一点儿关系都没有。j >= w[i]的意思是：在这轮循环中要尝试装入第i个物品，那么至少背包容量要有w[i]，即可以放下第i件物品。和第i-1件物品或者之前的物品的重量是多少没有关系。

可以找一组物品重量不按顺序排列的小数据，实际运行程序，有必要的话，跟踪程序，试试看？：）

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7435 学习 · 1159 问题

相似问题

回答 1

回答 1

回答 2

回答 1

回答 1