搜搜做题作业网一道类似于解不定方程的题目
来源：学生作业帮 编辑：搜搜做题作业网作业帮 分类：综合作业 时间：2024/07/11 19:35:06
一道类似于解不定方程的题目
现在有10元,5 元,2元三种面额.任意给定一个数字
1.判定可不可以用上面的三种面值凑出来
2.如果可以,给出每种的面额的数目
比方13=5+2+2+2+2
PS：不可以使用枚举法,有代码最好了,当然提供一下思路也可以
现在有10元,5 元,2元三种面额.任意给定一个数字
1.判定可不可以用上面的三种面值凑出来
2.如果可以,给出每种的面额的数目
比方13=5+2+2+2+2
PS：不可以使用枚举法,有代码最好了,当然提供一下思路也可以
用动态规划里面的背包来做,速度最快效率最好!
再问： 1.背包问题最后可以装不满,但是这里要凑够 2.背包问题是f[i,j]分成有没有a[i]的两种情况，这里还要考虑比方100有多张，比方330=2*100+50+4*20？
再答： 帮你打了个代码，你看看行不行。我这个没有任何处理，完全是纯暴力的背包，你可以自己加点东西，让输出好看一点什么的。如果对这个你不满意，再给你提供种思路，用深搜+剪枝，也很快出结果。我的是C语言的，应该看得懂吧？ #include #include bool bo[11000];//bo是背包数组，数组规模开多大看你求的那个数有多大 //bo[i]为true则表示可以满足总和为i，bo[i]为false则表示不行 int n,a[11000]; //因为你要记录路径，所以多开一个a数组，用来保存当前状态最后是由哪一个钱数存进来的 //比如说a[i]==2则表明i这个状态最后是由2来填充的 int main(){ scanf("%d",&n); memset(bo,0,sizeof(bo)); bo[0]=1; for(int i=2;i
再问： 1.背包问题最后可以装不满,但是这里要凑够 2.背包问题是f[i,j]分成有没有a[i]的两种情况，这里还要考虑比方100有多张，比方330=2*100+50+4*20？
再答： 帮你打了个代码，你看看行不行。我这个没有任何处理，完全是纯暴力的背包，你可以自己加点东西，让输出好看一点什么的。如果对这个你不满意，再给你提供种思路，用深搜+剪枝，也很快出结果。我的是C语言的，应该看得懂吧？ #include #include bool bo[11000];//bo是背包数组，数组规模开多大看你求的那个数有多大 //bo[i]为true则表示可以满足总和为i，bo[i]为false则表示不行 int n,a[11000]; //因为你要记录路径，所以多开一个a数组，用来保存当前状态最后是由哪一个钱数存进来的 //比如说a[i]==2则表明i这个状态最后是由2来填充的 int main(){ scanf("%d",&n); memset(bo,0,sizeof(bo)); bo[0]=1; for(int i=2;i