动态规划

背包问题

关于背包问题，其实有两种情况，第一个是0-1背包问题，第一个是部分背包问题

先来通过一个例子看看二者的区别吧有一个窃贼在偷窃一家商店时发现N件物品，每一件物品的价格为vi，重量为wi，他希望带走的东西越多越好，但是他的背包最多承重量为W，所以他要尽可能地带走性价比高的物品，他应该要怎么选择？ 0-1背包问题： 物品要么被带走，要么被留下，（需要做出0-1选择），小偷不能带走一个物品的一部分或者两次以上同一个物品 部分背包问题： 小偷可以带走一个物品的一部分，即物品可以被分割
0-1背包问题和部分背包问题的解法 0-1背包问题： 采用动态规划的解法我们用F(i, w)表示当拿到第i个物品，且背包剩余承重量为w的情况下背包里物品的总价值能达到的最大值，这里有两种情况，第一个是当前物品的承重量大于当前背包剩余承重量，即wi > w，那么这个时候当前的这个物品肯定是不能拿的，背包状态不变，依然等于上一个状态：即F(i, w) = F(i - 1, w);第二种情况是当前物品的重量小于当前背包的剩余承重量，那么这个时候就要比较了，无非就是比较两种情况，要么拿当前物品，要么不拿。当拿当前物品的时候，背包状态发生改变，即背包里物品的总价值会加上当前物品的价值，但是相应的背包剩余承重量会减去当前物品的重量，即F(i， w) = vi + F(i - 1, w - wi);要么不拿，背包状态不会发生改变，依然等于上一个状态：即F(i, w) = F(i - 1, w)；我们的目的就是要是的当前背包里物品的总价值能达到最大，这两种情况取最大值，即F(i, w) = max(F(i - 1, w), vi + F(i - 1, w - wi)) 通过上述分析，最终的状态转移方程就是：代码实现：
```
/*
 //w:每个物品的重
 //v:每个物品的价格
 //W:背包总的承重量
*/
const zo_knapsack_problem = function(w, v, W) {
 let F = new Array()
 for(let i = 0; i <= w.length; i++) {
     F[i] = new Array()
 }
 console.log(F)
 for(let i = 0; i <= W; i++) {
     F[0][i] = 0
 }
 for(let i = 0; i < w.length; i++) {
     F[i][0] = 0
 }
 for(let i = 1; i < w.length; i++) {
     for(let j = 1; j <= W; j++) {
         if(w[i] > j) {
             F[i][j] = F[i - 1][j]
         } else {
             F[i][j] = Math.max(F[i - 1][j], v[i] + F[i - 1][j - w[i]])
         }
     }
 }
 return F[w.length - 1][W]
}
const main = function() {
 const w = [0, 2,1,3,2], v = [0, 10,12,15,20], W = 5
 return zo_knapsack_problem(w, v, W)
}
```
部分背包问题： 采用贪心法首先计算出每种物品单位质量的价值，然后依次将单位价值最高的物品尽可能多的装入背包中：若将这种物品全部装入后背包仍未满，则考虑单位质量价值次高的物品，直至背包装满。可以看出，排序在这里是非常重要的。代码实现
```
const fractional_kanpsack = (goods, W) => {
 //先将每个物品按照价格排序
 let sumV = 0, idx = 0
 goods.sort(function(a, b) {
     return a.v - b.v
 })
 for(let i = 0; i < goods.length; i++) {
     if(goods[i][w] > W) {
         idx = i
         break
     }
     else {
         W -= goods[i][w]
         sumV += goods[i][v]
     }
 }
 return sumV + Math.floor(goods[idx][v] * (W / goods[idx][w]))
}
```

动态规划之背包问题

动态规划

背包问题

关于背包问题，其实有两种情况，第一个是0-1背包问题，第一个是部分背包问题

CATALOG