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］。

Answer 2

0-1背包问题物品有两种选择，要么放进去要么不放进去
而背包问题的话可以放部分，比如一斤糖可以放1/3斤 换句话说这里物品取值为（0，1）
而0-1背包问题物品只能取0和1两个值 望采纳

Answer 3

没什么区别