算法-完全背包

loading 2023年10月28日 42次浏览

其实和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]) // ...
        }
    }