有n种硬币，面值分别为v1, v2, ..., vn，每种都有无限多。给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值。
第一行两个整数，n，S（1≤n≤100， 0≤S≤100000）。 第二行n个整数vi-1...n(1≤vi≤S)。
第一行两个整数，分别表示硬币数目的最小值 a 和最大值 b 。无解则输出 -1 。 第二行 a 个整数分别表示使用的是第几种硬币。 第三行 b 个整数分别表示使用的是第几种硬币。
6 12 1 2 3 4 5 6
2 12 6 6 1 1 1 1 1 1 1 1 1 1 1 1
CJOJ:http://oj.changjun.com.cn/problem/detail/pid/1071
动态规划
看到这道题首先想到的是spfa算法。令每一个面值为一个点，若面值j=i+v[k]则连一条边（只是这么想，实际不用连边），那么分别用spfa跑出0->S的最短路径和最长路径。
这么想虽然没错，但会超时（70分）。下面会给出spfa代码，这里就不过多叙述。
那么正解是什么呢？动态规划。
我们以求最小值为例，定义Dmin[i]表示能凑出面值i的最少硬币数，用path_min[i]记录这个数量是从哪个面值转移过来的。那么我们就有Dmin[i]=min(Dmin[i-V[j]]+1)。 最后求路径的时候先令一个变量k=S，每次将k-path_min[k]压入一个vector中，再将k=path_min[k]，直到k==0。然后将vector排序，再输出。
而最大值的操作是类似的。
另外要注意的是，题中输出的应该是面值的编号，所以用一个Map[i]存下面值i对应的编号，所以压入vector的就是Map[k-path_min[k]]
spfa（TLE代码）
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> using namespace std; const int maxN=200; const int maxS=100050; const int inf=2147483647; int n,S; int V[maxN]; int Dmax[maxS]; int Dmin[maxS]; int path_max[maxS];//记路径 int path_min[maxS]; bool vis[maxS]; int Map[maxS];//因为最后要输出的是编号，所以为每一个面值都存一个编号 queue<int> Q; vector<int> arr; void spfa_min(); void spfa_max(); void dfs_min(int sum);//dfs求答案，但会爆栈 void dfs_max(int sum); int main() { memset(Dmax,-1,sizeof(Dmax)); memset(Dmin,-1,sizeof(Dmin)); memset(Map,-1,sizeof(Map)); cin>>n>>S; for (int i=1;i<=n;i++) { cin>>V[i]; if (Map[V[i]]==-1) Map[V[i]]=i;//记录面值i所对应的的编号i } spfa_min(); spfa_max(); cout<<Dmin[S]<<' '<<Dmax[S]<<endl; //dfs_min(S);cout<<endl; //dfs_max(S); int k=S;//手动写栈，排序 while (k>0) { arr.push_back(Map[k-path_min[k]]); k=path_min[k]; } sort(arr.begin(),arr.end()); for (int i=0;i<arr.size();i++) cout<<arr[i]<<' '; cout<<endl; k=S;//手动写栈，排序 arr.clear(); while (k>0) { //cout<<":AA"<<endl; arr.push_back(Map[k-path_max[k]]); k=path_max[k]; } sort(arr.begin(),arr.end()); for (int i=0;i<arr.size();i++) cout<<arr[i]<<' '; cout<<endl; return 0; } void spfa_min() { memset(vis,0,sizeof(vis)); Q.push(0); vis[0]=1; Dmin[0]=0; do { int u=Q.front(); Q.pop(); vis[u]=0; for (int i=1;i<=n;i++) if (u+V[i]<=S) if ((Dmin[u]+1<Dmin[u+V[i]])||(Dmin[u+V[i]]==-1)) { Dmin[u+V[i]]=Dmin[u]+1; path_min[u+V[i]]=u; if (vis[u+V[i]]==0) { Q.push(u+V[i]); vis[u+V[i]]=1; } } } while (!Q.empty()); return; } void spfa_max() { memset(vis,0,sizeof(vis)); while (!Q.empty()) Q.pop(); Q.push(0); vis[0]=1; Dmax[0]=0; do { int u=Q.front(); Q.pop(); vis[u]=0; for (int i=1;i<=n;i++) if (u+V[i]<=S) if ((Dmax[u]+1>Dmax[u+V[i]])||(Dmax[u+V[i]]==-1)) { Dmax[u+V[i]]=Dmax[u]+1; path_max[u+V[i]]=u; if (vis[u+V[i]]==0) { vis[u+V[i]]=1; Q.push(u+V[i]); } } } while (!Q.empty()); return; } void dfs_min(int sum) { if (sum==0) return; dfs_min(path_min[sum]); cout<<Map[sum-path_min[sum]]<<' '; return; } void dfs_max(int sum) { if (sum==0) return; dfs_max(path_max[sum]); cout<<Map[sum-path_max[sum]]<<' '; return; }动态规划
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int maxN=200; const int maxS=200000; const int inf=1000000000; int n,S; int V[maxN]; int Dmin[maxS]; int Dmax[maxS]; int path_min[maxS]; int path_max[maxS]; int Map[maxS]; vector<int> arr;//输出时要临时存放面值的编号并排序 int main() { memset(Map,-1,sizeof(Map)); cin>>n>>S; for (int i=1;i<=n;i++) { cin>>V[i]; if (Map[V[i]]==-1) Map[V[i]]=i; } for (int i=1;i<=S;i++) { Dmin[i]=inf;//初始值，最小值最大，最大值最小 Dmax[i]=-inf; } Dmin[0]=0; Dmax[0]=0; for (int i=1;i<=S;i++) { for (int j=1;j<=n;j++) if (i-V[j]<0) continue; else//DP { if (Dmin[i]>Dmin[i-V[j]]+1) { Dmin[i]=Dmin[i-V[j]]+1; path_min[i]=i-V[j]; } if (Dmax[i]<Dmax[i-V[j]]+1) { Dmax[i]=Dmax[i-V[j]]+1; path_max[i]=i-V[j]; } } } cout<<Dmin[S]<<' '<<Dmax[S]<<endl; int k=S; arr.clear(); while (k>0)//输出方案 { arr.push_back(Map[k-path_min[k]]); k=path_min[k]; } sort(arr.begin(),arr.end()); for (int i=0;i<arr.size();i++) cout<<arr[i]<<' '; cout<<endl; k=S; arr.clear(); while (k>0) { arr.push_back(Map[k-path_max[k]]); k=path_max[k]; } sort(arr.begin(),arr.end()); for (int i=0;i<arr.size();i++) cout<<arr[i]<<' '; cout<<endl; return 0; }转载于:https://www.cnblogs.com/SYCstudio/p/7137823.html
