高考问答给京东客服人员打差评:两种算法
来源：百度文库 编辑：高考问答 时间：2024/05/07 09:35:38
"算法设计与分析"的上机题:用动态规划法实现0-1背包问题,用贪心法和动态规划法实现普通背包问题.还有:为什么贪心法不能实现0-1背包问题?举出反例,还要比较这两种算法的适用范围
请各位编程高手来看一下.
请各位编程高手来看一下.
因为0-1背包是最优子结构问题，贪心法解决不了最优子结构问题。
反例：例如最后剩下三件物品，背包的剩余重量空间为5，其中的一件重量为4，单位价值为10；另一件重量为3，单位价值为9；还有一件的重量为2，单位价值为9。
根据贪心法应该选择重量为5的，而实际情况应该选择另外两件