首页 > 代码库 > 杭电 1284 钱币兑换问题【完全背包求方案总数】
杭电 1284 钱币兑换问题【完全背包求方案总数】
解题思路：因为对于完全背包的状态转移方程f[v]=max(f[v],f[v-c[i]]+w[i])已经记录了所有背包组成的方案，只不过通常问的是求最大值，现在要求方案总数
即为 f[v]=sum(f[v],f[v-c[i]+w[i]]),
Problem Description
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N，N小于32768。
Output
对应每个输入，输出兑换方法数。
Sample Input
2934 12553
Sample Output
718831 13137761
#include<stdio.h>#include<string.h>long long f[50000];int a[4];long long sum(long long a,long long b){ return a+b;}int main(){ int n,i,v; while(scanf("%d",&n)!=EOF) { memset(f,0,sizeof(f)); f[0]=1; a[1]=1; a[2]=2; a[3]=3; for(i=1;i<=3;i++) { for(v=a[i];v<=n;v++) f[v]=sum(f[v],f[v-a[i]]); } printf("%I64d\n",f[n]); } }
杭电 1284 钱币兑换问题【完全背包求方案总数】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。