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;

}