回溯法解决背包问题

[ZhengXingchi]

已知背包容量为100 共有5个物品 每个物品重量分别为[10,20,30,40,60] 每个物品价值分别为[20,30,65,40,60] 求背包能装下的物品的最大价值，每个物品不能进行拆分

[ZhengXingchi]

参考文献

JavaScript实现利用回溯法解决0-1背包问题

[ZhengXingchi]

 let weight = 100
    let num = 5
    let w = [10, 20, 30, 40, 60]
    let v = [20, 30, 65, 40, 60]
    let path = []
    let maxValue = 0
    function search(i) {
      if (i >= 5) {
        findMax(path)
      }
      else {
        path[i] = 0
        search(i + 1)
        path[i] = 1
        search(i + 1)
      }
    }

    function findMax(path) {
      let wei = 0
      let val = 0
      for (let i = 0; i < path.length; i++) {
        if (path[i] === 1) {
          wei = wei + w[i]
          val = val + v[i]
        }
      }
      if (wei <= weight) {
        if (val > maxValue) {
          maxValue = val
          console.log('最大价值为' + maxValue);

          console.log(path);
        }
      }
    }

    search(0)