POJ 1252 Euro Efficiency(BFS or 完全背包)

http://poj.org/problem?id=1252

题意:

       有6种货币,它们的面值分别为1,v2,v3,v4,v5,v6. 且它们面值最大值小于100. 最小值始终是1(就是那个v1). 现在的问题是 要你用尽量少的这6种货币构造1到100的所有面值的金钱. 问你构造这100个数平均需要多少个货币? 最多需要多少个货币?

注意: 这里的构成不仅包含相加, 还能相减. 即假设货币面值为:要1 3 5 7 9 11 时, 你需要构造4. 那么你可以用1+3, 你也可以用5-1来构造, 你还可以用1+1+1+1来构造.

分析:

解法一: BFS广度优先搜索.

       由于要构造1-100, 这100个数, 问我们每个数最少需要几个货币即可. 且原本的货币还能减法运算, 所以我们在原来6种货币的基础上再添加6种货币. 这6种新货币面积就是原来6中货币面值的负数.

       我们令dist[i]==x 表示构造面值为i金钱最少需要x个货币.

       初始值dist为全INF. 且dist[0]==0.

       之后我们进行BFS即可. 大体思想就是我们从u点出发, 如果u点到某个点v的距离小于 v点原本的距离, 那么我们就找到了v点的一种更优的构造方法. 那么由v点构造的所有其他点也需要更新, 所以v点入队列, 下次取出v点进行BFS即可更新由v点构造的所有其他后继节点的dist值.

       当队列为空时, 说明构造完毕,退出统计结果即可.

       有一点需要注意: 由于每次+货币的面值可正可负, 所以就算我们只需要构造100面值内的金钱, 也有可能在构造100的过程中超过了100. 比如货币面值为1 51 91 92 93 94 时, 构造100的最优方法为51+51-1-1. 那么我们就需要102面值金钱的构造dist[102] 才能正确的推出dist[100]. (想想是不是) 所以BFS的范围不是1-100,而是应该1到更大值, 但是这个值到底需要多大, 必须要严谨证明才行. 程序实现中我用的200能得到正确结果.

解法二:两次完全背包DP.

       由于构造一个面值的金钱需要加减货币价值, 所以对于如下构造:

100=55+55-4-4-2 我们可以定义55+55作为最大付款数, -4-4-2为找零数,100是最终付款数.

       其实我们不妨把每个上面的构造过程分成两部分: 构造最大付款数 和 找零.

       第一步构造最大付款数: (一次完全背包过程)

       令dp[i][j]==x 表示用前i种货币相加能得到的面值为j的金钱时, 最少需要x个货币.

       初始值dp全为INF(无穷大), dp[0][0]=0.

       状态转移: dp[i][j] = min( dp[i-1][j] , dp[i][j-val[i]]+1 )

       前者表示第i种货币一个都不用, 后者表示至少用1个第i种货币.

       最终dp[n][0]到dp[n][maxn]都是我们需要的数据. 它们表示当我们只加不减的时候最少需要多少个货币能达到金钱面值.

       第二步找零: (另一次完全背包过程)

       由上一步继承的dp结果, 我们现在可以令dp[i][j]==x 表示当决策完前i个物品后(如果选第i种物品,就表示在当前货币值得基础上减去val[i])具有金钱面值为j时, 最少需要x个货币.

       初始值: 上一轮DP的结果.

       状态转移: dp[i][j-val[i]] = min( dp[i-1][j-val[i]] , dp[i][j]+1)

       前者表示第i种货币一个都不减, 后者表示至少减去1个第i种货币.

       最终dp[n][1] 到dp[n][100]都是我们需要的数据.

       程序实现用的滚动数组, 所以dp只有[j]这一维.

解法三:看成12种货币做, 1次完全背包

       另外可以把6个货币直接看成12个不同的货币, 然后做一次完全背包吗?

       可以, 不过加货币和减货币的递推顺序不同, 加货币是从货币总值小到大递推, 而减货币是从货币总值大到小递推. 对于不同val[i]不同处理即可.

       程序中的maxn我是自己测试的,不过网上有人给出了这个maxn的范围证明:

       ” 最多付款的数目(比如人民币中付款49，则可以先付50，找回1，则50称为最多付款的数目)肯定小于(100/val[1])* val [6]+100，因为如果达到这个值，则需要找零至少100/ val [1]=100才能回到[1,100]的范围，这样还不如直接用val [1]来付款”

AC代码1: BFS做法

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 1e8
const int maxn=200+5;
int n=12;//正负一共12种货币
int val[12+5];//每种货币的价值
int dist[maxn];

void BFS()
{
    //初始化
    queue<int> Q;
    for(int i=1;i<maxn;i++)
        dist[i]=INF;
    dist[0]=0;
    Q.push(0);

    //BFS遍历1-200内所有节点,找每个dist[i]的最小值
    while(!Q.empty())
    {
        int u=Q.front(); Q.pop();
        for(int i=1;i<=n;i++)
        {
            int v=u+val[i];
            if(v>=1 && v<maxn && dist[u]+1<dist[v] )
            {
                dist[v] = dist[u]+1;
                Q.push(v);
            }
        }
    }

    //统计结果:sum为总数,max_step为最大数
    int sum=0,max_step=0;
    for(int i=1;i<=100;i++)
    {
        max_step = max(max_step,dist[i]);
        sum += dist[i];
    }
    printf("%.2f %d\n",sum/100.0,max_step);
    //如果上面改成%.2lf提交,那么C++AC,G++WA.
}

int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        for(int i=1;i<=6;i++)
            scanf("%d",&val[i]);
        for(int i=7;i<=n;i++)
            val[i]=-val[i-6];
        BFS();//处理问题
    }
    return 0;
}

AC代码2: 2次完全背包

#include<cstring>
#include<cstdio>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=2000+5;

int n=6;   //货币种类数
int val[7];//货币面值
int dp[maxn];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        //读输入数据
        for(int i=1;i<=6;i++)
            scanf("%d",&val[i]);

        //初始化
        for(int i=0;i<maxn;i++)
            dp[i]=INF;
        dp[0]=0;

        //正向DP,更新 dp[最大付款数]
        for(int i=1;i<=n;i++)
        {
            for(int j=val[i];j<maxn;j++)
                dp[j]= min(dp[j], dp[j-val[i]]+1);
        }

        //反向DP,更新 dp[最终付款数]
        for(int i=1;i<=n;i++)
        {
            for(int j=maxn-1;j>=val[i];j--)
                dp[j-val[i]] = min(dp[j-val[i]], dp[j]+1);
        }

        //统计结果输出
        int sum=0,max_val=0;
        for(int i=1;i<=100;i++)
        {
            sum += dp[i];
            max_val=max(max_val,dp[i]);
        }
        printf("%.2f %d\n",sum/100.0,max_val);

    }
}

AC带代码3:   一次完全背包

#include<cstring>
#include<cstdio>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=2000+5;

int n=12;   //货币种类数
int val[13];//货币面值
int dp[maxn+100];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        //读输入数据,构造12种货币
        for(int i=1;i<=6;i++)
        {
            scanf("%d",&val[i]);
            val[i+6] = -val[i];
        }

        //初始化
        for(int i=0;i<maxn;i++)
            dp[i]=INF;
        dp[0]=0;

        //递推过程
        for(int i=1;i<=n;i++)
        {
            if(val[i]>0)
            {
                for(int j=val[i];j<maxn;j++)
                    dp[j]= min(dp[j], dp[j-val[i]]+1);
            }
            else if(val[i]<0)
            {
                int v = -val[i];
                for(int j=maxn-1;j>=v;j--)
                    dp[j-v] = min(dp[j-v], dp[j]+1);
            }
        }

        //统计结果输出
        int sum=0,max_val=0;
        for(int i=1;i<=100;i++)
        {
            sum += dp[i];
            max_val=max(max_val,dp[i]);
        }
        printf("%.2f %d\n",sum/100.0,max_val);

    }
}

POJ 1252 Euro Efficiency(BFS or 完全背包)