CJOJ 1071 【Uva】硬币问题（动态规划）
Description
有n种硬币，面值分别为v1, v2, ..., vn，每种都有无限多。给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值。
Input
第一行两个整数，n，S（1≤n≤100， 0≤S≤100000）。
第二行n个整数vi-1...n(1≤vi≤S)。
Output
第一行两个整数，分别表示硬币数目的最小值 a 和最大值 b 。无解则输出 -1 。
第二行 a 个整数分别表示使用的是第几种硬币。
第三行 b 个整数分别表示使用的是第几种硬币。
Sample Input
6 12
1 2 3 4 5 6
Sample Output
2 12
6 6
1 1 1 1 1 1 1 1 1 1 1 1
Http
CJOJ:http://oj.changjun.com.cn/problem/detail/pid/1071
Source
动态规划
解决思路
看到这道题首先想到的是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;
}