其实和01背包基本一样的,唯一的区别是完全背包遍历背包时需要从前往后遍历,才能实现重复放入物品,考虑以下两种情况:
1. 求组合
组合就是[1, 0]和[0, 1]算一个东西,不看顺序。
此时外层遍历物品,内层遍历背包:
for(let i = 0 ; i < nums.length ; i++) {
for(let j = nums[i] ; j <= weight ; j++) {
// ...
}
}
2. 求排列
排列就是[1, 0]和[0, 1]不算一个东西,看顺序。
此时外层遍历背包,内层遍历物品:
for(let j = 0 ; j <= weight ; j++) {
for(let i = 0 ; i < nums.length ; i++) {
if(j >= nums [i]) // ...
}
}