HDU3591找零，背包

题目大概的意思就是：小强用硬币买东西，硬币有N种，面值为Vi，店家有各种硬币都有无限个，而小强只有Ci个（分别对应Vi）

问最小交易硬币数，就是一个有找零的背包问题啦。

我的上一篇博客跟这hdu3591的类型非常非常接近，所以我很快就写完，并且很快地WA了无数次。

后来很苦恼，看看别人写的代码，他们的思想大概是这样子。用dp2去记载找零，就是dp2[i]=min{dp2[i],dp2[i-V]+1 } V为要付的总款

之后再从V到INF处得到ans=min{ans,dp[i]+dp2[i-V]};

思路是很清晰啦，很快我又CODE了一段。

马上又WA了无数次。

正当我无力时候，我发现！！！！原来是我的ZeroOnePack的参数写错了...第二个版本，改了参数后，马上就Accepted了！！！！！！！

先发个第二个版本的。

#include"stdio.h"

#include"string.h"

#define m 105

#define m3 20005

int V=m3;

int N;

int c[m],n[m],dp[m3+1],dp2[m3+1];

int min(int a,int b){

    return a<b?a:b ;

}

void ZeroOnePack(int vol,int val){

    int i;

    for(i=V;i>=vol;i--)

        dp[i]=min(dp[i],dp[i-vol]+val);

}

void CompletePack(int vol,int val){

    int i;

    for(i=vol;i<=V;i++)

        dp[i]=min(dp[i],dp[i-vol]+val);

}

void MultPack(int vol,int val,int num){

    int k;

    if(num*vol>=V){

      CompletePack(vol,val);

      return ;

    }

     k=1;

    while(k<num){

      ZeroOnePack(k*vol,k*val);

      num-=k;

      k<<=1;

    }

    ZeroOnePack(num*vol,num*val);

}

int main(){

    int i,j,V1,ca=1,ans;

    while(scanf("%d%d",&N,&V1)&&(N||V1)){

        memset(dp,63,sizeof(dp));

        dp[0]=0;

        memset(dp2,63,sizeof(dp2));

        dp2[0]=0;

       for(i=1;i<=N;i++)

           scanf("%d",&c[i]);

       for(i=1;i<=N;i++)

           scanf("%d",&n[i]);

       //给钱

       for(i=1;i<=N;i++)

           MultPack(c[i],1,n[i]);

       //找零

       for(i=1;i<=N;i++)

           for(j=c[i];j<=V;j++)

               dp2[j]=min(dp2[j],dp2[j-c[i]]+1);

        ans=0xfffffff;

        for(i=V1;i<=V;i++)

           ans=min(ans,dp[i]+dp2[i-V1]);

      printf("Case %d: %d\n",ca++,ans==0xfffffff?-1:ans);

    };

    return 0;

}

10325750

2014-03-17 22:21:06

Accepted

3591

78MS

388K

1403 B

deron

后来，我又把我第一个版本给改了一下，交了。毫无问题，Accepted

#include"stdio.h"

#include"string.h"

#define m 103

#define m3 20003

int V=m3;

int N;

int c[m],n[m],dp[m3+1];

int min(int a,int b){

    return a<b?a:b ;

}

void ZeroOnePack(int vol,int val){

    int i;

    for(i=V;i>=vol;i--)

        dp[i]=min(dp[i],dp[i-vol]+val);

}

void CompletePack(int vol,int val){

    int i;

    for(i=vol;i<=V;i++)

        dp[i]=min(dp[i],dp[i-vol]+val);

}

void MultPack(int vol,int val,int num){

    int k;

    if(num*vol>=V){

      CompletePack(vol,val);

      return ;

    }

     k=1;

    while(k<num){

      ZeroOnePack(k*vol,k*val);

      num-=k;

      k<<=1;

    }

    ZeroOnePack(num*vol,num*val);

}

int main(){

    int i,j,V1,ca=1;

    while(scanf("%d%d",&N,&V1)&&(N||V1)){

           for(i=1;i<=V;i++)

              dp[i]=0xfffffff;

             dp[0]=0;

       for(i=1;i<=N;i++)

           scanf("%d",&c[i]);

       for(i=1;i<=N;i++)

           scanf("%d",&n[i]);

       //给钱

       for(i=1;i<=N;i++)

           MultPack(c[i],1,n[i]);

       //找零

       for(i=1;i<=N;i++)

           for(j=V-c[i];j>0;j--)

               dp[j]=min(dp[j],dp[j+c[i]]+1);

            if(dp[V1]==0xfffffff)

            dp[V1]=-1;

             printf("Case %d: %d\n",ca++,dp[V1]);

    };

    return 0;

}

10325819

2014-03-17 22:30:06

Accepted

3591

62MS

308K

2745 B

deron

其思想就是找零时候做一次01背包，思路跟第二个版本也差不多。