2024-03-06：用go语言，每一种货币都给定面值val[i]，和拥有的数

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

packagemain
import(
"fmt"
)
constMAXN=101
constMAXM=100001
varval[MAXN]int
varcnt[MAXN]int
vardp[MAXM]bool
varn,mint
funcmain(){
inputs:=[]int{3,10,
1,2,4,2,1,1,
2,5,
1,4,2,1,
0,0}
ii:=0
foriin=inputs[ii]
ii++
m=inputs[ii]
ii++
ifn!=0||m!=0{
fori:=1;i<=n;i++{
val[i]=inputs[ii]
ii++
}
fori:=1;i<=n;i++{
cnt[i]=inputs[ii]
ii++
}
ans:=compute()
fmt.Println(ans)
}else{
break
}
}
}
funccompute()int{
fori:=1;i<=m;i++{
dp[i]=false
}
dp[0]=true
fori:=1;i<=n;i++{
ifcnt[i]==1{
forj:=m;j>=val[i];j--{
ifdp[j-val[i]]{
dp[j]=true
}
}
}elseifval[i]*cnt[i]>m{
forj:=val[i];j<=m;j++{
ifdp[j-val[i]]{
dp[j]=true
}
}
}else{
formod:=0;modtrueCnt:=0
forj,size:=m-mod,0;j>=0&&size<=cnt[i];j-=val[i]{
trueCnt+=boolToInt(dp[j])
size++
}
forj,l:=m-mod,m-mod-val[i]*(cnt[i]+1);j>=1;j-=val[i]{
ifdp[j]{
trueCnt--
}else{
iftrueCnt!=0{
dp[j]=true
}
}
ifl>=0{
trueCnt+=boolToInt(dp[l])
}
l-=val[i]
}
}
}
}
ans:=0
fori:=1;i<=m;i++{
ifdp[i]{
ans++
}
}
returnans
}
funcboolToInt(bbool)int{
ifb{
return1
}
return0
}