完全背包

完全背包和01背包的区别：
完全背包：物品可以无限使用，遍历顺序没有强制规定，可以先物品后背包，反之亦可以

01背包： 物品只能使用一次，遍历顺序为先物品后背包

go代码实现

package main
import (
    "fmt"
)
/*
wei,是重量数组
value，是价值数组
bagWei， 是背包容量

返回值：是背包可以装的物品的最大价值
*/

//先遍历背包，后遍历物品
func CompletePack1(wei, value []int ,bagWei int) int {
    //初始化，默认为0
    dp := make([]int,bagWei+1)
    for i:=0; i<len(dp); i++ {
        for j := 0; j<len(wei); j++ {
            if wei[j]<=i {
                dp[i] = max(dp[i],dp[i-wei[j]]+value[j])
            }
        }
    }
    return dp[bagWei]
}

//先遍历物品，再遍历背包

func CompletePack2(wei, value []int, bagWei int) int {
    dp := make([]int,bagWei+1)
    for i:=0; i<len(wei); i++ {
        for j:=wei[i]; j<len(dp);j++ {
            dp[j]= max(dp[j],dp[j-wei[i]]+value[i])
        }
    }
    return dp[bagWei]
}
func max(a,b int) int {
    if a>b {
        return a
    } else {
        return b
    }
}

func main() {
    wei := []int{1,3,4}
    value := []int{15,20,30}
    result := CompletePack1(wei,value,4)
    fmt.Println(result)
}

零钱兑换II

问题描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

思路

这个题目可以用完全背包来解决

1 确定dp
dp[i] 指的是背包容量为i时，可以凑出的组合数
组合数不考虑顺序
2 确定状态转换规则

dp[j] = dp [j] + dp [j- coins[i]]
什么意思呢？
dp[j] 是指当前容量j的组合数，但是现在来了一个硬币 coins[i] ,组合数必然增加，即需要加上dp [j- coins[i]] 。

3 初始化
dp[0]=1

4 遍历顺序
先物品后背包 ：得到组合数
先背包后物品： 得到排列数

5 举例
......

go代码实现

func change(amount int, coins []int) int {
    res := make([]int, amount+1)
    res[0]=1
    for i := 0;i<len(coins); i++ {
        for j:=coins[i]; j<amount+1; j++ {
            res[j]= res[j]+res[j-coins[i]] 
        }
        fmt.Println(res)
    }
    return res[amount]
}