GO题解 | #01背包#

go解题答案

• 思路概括：动态规划

• 思路核心：
  1、转移变量为商品和体积，值是最大重量
  2、d[i][j] 表示 经过挑选i轮商品在j体积下最大值，此时并不一定只有i商品
  3、转移方程为 case1:如果体积不够这一次的商品，则等于上一次的最佳方案 d[i][j]=d[i-1][j]
  4、case2:如果体积够这一次的商品，则等于上一轮时让出这次商品的体积最佳值d[i-1][j-vw[i-1][0]]+这次的值vw[i-1][1]

  func knapsack( V int ,  n int ,  vw [][]int ) int {
    // write code here
    if V==0||n==0|| vw==nil {
        return 0
    }
  
     d := make([][]int, n+1)
  
    for k := 0;k < n+1; k++ {
        d[k] = make([]int, V+1) // 要初始化，否则空指针注意从1开始，所以是V+2
    }
    for i:=1;i<=n;i++{
        for j:=1;j<=V;j++{
            if j<vw[i-1][0]{
                d[i][j]=d[i-1][j]
            }else{
                a:=d[i-1][j] // 不放的结果
                b:=d[i-1][j-vw[i-1][0]]+vw[i-1][1] //  放的结果
                d[i][j]= Max(a,b) //转移方程
  
            }
  
        }
    }
    return d[n][V]
  }

  如果有帮助请点个赞哦， 更多文章请看我的博客

  题主背景

• 从业8年——超级内卷500Q技术经理——目前专注go和微服务架构