golang力扣leetcode 125背包问题（二）

package main
//state: dp[i][j]前i个物品，j的重量，表示的最大价值
//function: dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]]+V[i-1])
//intialize:dp = 0
//answer: dp[len(A)][m]
/**
 * @param m: An integer m denotes the size of a backpack
 * @param A: Given n items with size A[i]
 * @param V: Given n items with value V[i]
 * @return: The maximum value
 */
func backPackII(m int, A []int, V []int) int {
  dp := make([][]int, len(A)+1)
  for i := range dp {
    dp[i] = make([]int, m+1)
  }
  for i := 1; i <= len(A); i++ {
    for j := 0; j <= m; j++ {
      //容量不够，不装
      if j < A[i-1] {
        dp[i][j] = dp[i-1][j]
      } else {
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]]+V[i-1])
      }
    }
  }
  return dp[len(A)][m]
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}
func backPack2(m int, A []int, V []int) int {
  dp := make([]int, m+1)
  for i := 1; i <= len(A); i++ {
    for j := m; j >= A[i-1]; j-- {
      dp[j] = max(dp[j], dp[j-A[i]]+V[i])
    }
  }
  return dp[m]
}