2024-03-06：用go语言，每一种货币都给定面值val[i]，和拥有的数量cnt[i]，
想知道目前拥有的货币，在钱数为1、2、3...m时，能找零成功的钱数有多少？
也就是说当钱数的范围是1~m，返回这个范围上有多少可以找零成功的钱数。
比如只有3元的货币，数量是5张，
m = 10。
那么在1~10范围上，只有钱数是3、6、9时，可以成功找零，
所以返回3，表示有3种钱数可以找零成功。
答案2024-03-06：
来自左程云。
灵捷3.5
大体步骤如下：
1.创建一个数组val，存储每种货币的面值，数组cnt存储拥有的每种货币的数量。
2.使用动态规划，创建一个长度为m 1的bool数组dp，dp[i]表示钱数i是否可以找零。
3.初始化dp[0]为true，因为钱数为0时不需要找零，即为成功找零。
4.遍历每种货币，根据面值和数量的不同情况分别处理找零的逻辑。
4.a.如果数量为1，遍历更新dp数组，当j >= val[i]时，如果dp[j-val[i]]为true，则说明钱数j可以成功找零。
4.b.如果数量大于1且面值*数量大于m，遍历更新dp数组，当j >= val[i]时，如果dp[j-val[i]]为true，则说明钱数j可以成功找零。
4.c.如果数量大于1且面值*数量小于等于m，使用更复杂的逻辑更新dp数组，计算出钱数j成功找零的情况。
5.遍历dp数组，计算找零成功的钱数有多少。
6.返回钱数成功找零的总数量。
总的时间复杂度为O(n*m)，其中n为货币种类数，m为钱数范围。
总的额外空间复杂度为O(m)，主要是dp数组的空间。
go完整代码如下：
代码语言：javascript复制package main
import (
"fmt"
)
const MAXN = 101
const MAXM = 100001
var val [MAXN]int
var cnt [MAXN]int
var dp [MAXM]bool
var n, m int
func main() {
inputs := []int{3, 10,
1, 2, 4, 2, 1, 1,
2, 5,
1, 4, 2, 1,
0, 0}
ii := 0
for ii < len(inputs) {
n = inputs[ii]
ii
m = inputs[ii]
ii
if n != 0 || m != 0 {
for i := 1; i <= n; i {
val[i] = inputs[ii]
ii
}
for i := 1; i <= n; i {
cnt[i] = inputs[ii]
ii
}
ans := compute()
fmt.Println(ans)
} else {
break
}
}
}
func compute() int {
for i := 1; i <= m; i {
dp[i] = false
}
dp[0] = true
for i := 1; i <= n; i {
if cnt[i] == 1 {
for j := m; j >= val[i]; j-- {
if dp[j-val[i]] {
dp[j] = true
}
}
} else if val[i]*cnt[i] > m {
for j := val[i]; j <= m; j {
if dp[j-val[i]] {
dp[j] = true
}
}
} else {
for mod := 0; mod < val[i]; mod {
trueCnt := 0
for j, size := m-mod, 0; j >= 0 && size <= cnt[i]; j -= val[i] {
trueCnt = boolToInt(dp[j])
size
}
for j, l := m-mod, m-mod-val[i]*(cnt[i] 1); j >= 1; j -= val[i] {
if dp[j] {
trueCnt--
} else {
if trueCnt != 0 {
dp[j] = true
}
}
if l >= 0 {
trueCnt = boolToInt(dp[l])
}
l -= val[i]
}
}
}
}
ans := 0
for i := 1; i <= m; i {
if dp[i] {
ans
}
}
return ans
}
func boolToInt(b bool) int {
if b {
return 1
}
return 0
}
