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完整代码如下：

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
}

本作品采用《CC 协议》，转载必须注明作者和本文链接