Question

背包问题和0-1背包问题有什么区别

Answer 1

背包问题和0－1背包问题区别为：循环变量不同、约束条件不同、最大总价值不同。

一、循环变量不同

1、背包问题：背包问题须先求出列坐标j较小的元素，故让循环变量j的值从小到大递增。

2、0－1背包问题：0－1背包问题须先求出列坐标j较大的元素，故让循环变量j的值从大到小递减。

二、约束条件不同

1、背包问题：背包问题的约束条件是给定几种物品，物品可以取无限次。

2、0－1背包问题：0－1背包问题的约束条件是给定几种物品，物品只可以取一次。

三、最大总价值不同

1、背包问题：背包问题若取了1件第i个物品，则总容量变为j－W［i］，剩下的仍可以在前i件物品中去取，其最大总价值为B［i］［j－W［i］］ ＋ P［i］。

2、0－1背包问题：0－1背包问题若取了1件第i个物品，则总容量变为j－W［i］，剩下的只能在前i－1件物品中去取了，其最大总价值为B［i－1］［j－W［i］］ ＋ P［i］。