Main » 2012 November 1 » 硬币问题
6:05 PM 硬币问题 | |
【题目描述】有 n 种硬币，面值分别为 v1, v2.....vn ，每种都有无限多。给定非负整数 S ，可以选用多少个硬币，使得面值之和恰好为 S ？输出硬币数目的最小值和最大值。 【输入格式】第一行两个整数 n, S (1 < n < 100, 0 < S < 100000)。 第二行 n 个整数 v{i=1..n} (1 < vi < S) 。 【输出格式】第一行两个整数，分别表示硬币数目的最小值 a 和最大值 b 。无解则输出 -1 。 第二行 a 个整数分别表示使用的是第几种硬币。 第三行 b 个整数分别表示使用的是第几种硬币。 【样例输入】6 12 【样例输出】2 12 【提示】样例是特殊的，编号和面值是相同的。你编写程序的时候要注意输出编号而不是面值。 结果按编号升序输出。 若有多组解，输出字典序小的。 【来源】算法竞赛入门经典 例题 9-3 题解： 本题是一个较水的动态规划，主要是输出路径还有点难度。对于每个状态记录其的父节点。。没了，就是这么简单。 代码： C++语言:made by PaulInsider!
#include #include #include #include #include using namespace std; vector<int>ans; int n,m,w[200]; int q[100005][2]={0},a[100005][2]={0}; int main() { freopen ("kouka.in","r",stdin); freopen ("kouka.out","w",stdout); cin>>n>>m; for (int i=1;i<=n;i++) { cin>>w[i]; } for (int i=0;i<=m;i++) { q[i][0]=99999; q[i][1]=99999; a[i][0]=-1; a[i][1]=-1; } q[0][0]=0; for (int i=1;i<=m;i++) { for (int j=0;j<=n;j++) { if (i-w[j]>=0&&q[i][0]>q[i-w[j]][0]+1) { q[i][0]=q[i-w[j]][0]+1; q[i][1]=j; } } } a[0][0]=0; for (int i=1;i<=m;i++) { for (int j=1;j<=n;j++) { if (i-w[j]>=0&&a[i-w[j]][0]!=-1&&a[i-w[j]][0]+1>a[i][0]) { a[i][0]=a[i-w[j]][0]+1; a[i][1]=j; } } } cout<<q[m][0]<<' '<<a[m][0]<<endl; int tmp; tmp=m; while (q[tmp][1]!=99999) { ans.push_back(q[tmp][1]); tmp=tmp-w[q[tmp][1]]; } sort(ans.begin(),ans.end()); for (int i=0;i<ans.size();i++) cout<<ans[i]<<' '; cout<<endl; tmp=m; ans.clear(); while (a[tmp][1]!=-1) { ans.push_back(a[tmp][1]); tmp=tmp-w[a[tmp][1]]; } sort(ans.begin(),ans.end()); for (int i=0;i<ans.size();i++) cout<<ans[i]<<' '; return 0; } | |
|
| |
| Total comments: 0 | |