首页 > ACM题库 > HDU-杭电 > HDU 1284 钱币兑换问题-背包问题-[解题报告] C++
2013
12-04

HDU 1284 钱币兑换问题-背包问题-[解题报告] C++

钱币兑换问题

问题描述 :

在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

输入:

每行只有一个正整数N,N小于32768。

输出:

对应每个输入,输出兑换方法数。

样例输入:

2934
12553

样例输出:

718831
13137761

一.
经典完全背包
#include<iostream>
using namespace std;
int f[32768];
int volume[4]={0,1,2,3};
int main()
{
	f[0] = 1;
    for(int i = 1; i<=3; i++)
	{
		for(int j = volume[i]; j<32768; j++)
		{
			f[j] += f[j - volume[i]];
		}
	}
	int n;
	while(cin>>n)
		cout<<f[n]<<endl;
	return 0;
}

二.
找由几个3和几个2组成
这个方法这道题来说明显比背包优化了空间复杂度和时间复杂度
#include<iostream>
using namespace std;
int n;
int main()
{
	while(cin>>n)
	{
	int s = n/3 +1;    //由3组成的情况
    for(int i=0; i<=n/3; i++)
	     s+=(n - 3*i)/2;   //加上由2组成的
		cout<<s<<endl;
	}
	return 0;
}

三.网上还有用母函数的解决的,我没写过就不帖代码了


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。