算法训练营day38(补)，动态规划6

package main

func max(a, b int) int {

  if a > b {

    return a

  }

  return b

}

背包最大重量为4。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

每件商品都有无限个！

问背包能背的物品最大价值是多少？

func package03(weight, value []int, bagweight int) int {

  dp := make([]int, bagweight+1)

//遍历物品

  for i := 0; i < len(weight); i++ {  

 //遍历背包容量

    for j := weight[i]; j <= bagweight; j++ {

      dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

    }

  }

  return dp[bagweight]

}

//518. 零钱兑换 II

//求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];

func change(amount int, coins []int) int {

  dp := make([]int, amount+1)

  dp[0] = 1

  for i := 0; i < len(coins); i++ {

    for j := coins[i]; j <= amount; j++ {

      dp[j] += dp[j-coins[i]]

    }

  }

  return dp[amount]

}

//377. 组合总和 Ⅳ

func combinationSum4(nums []int, target int) int {

  dp := make([]int, target+1)

  dp[0] = 1

  for j := 0; j <= target; j++ {

    for i := 0; i < len(nums); i++ {

      if j >= nums[i] {

        dp[j] += dp[j-nums[i]]

      }

    }

  }

  return dp[target]

}