简单的完全背包HDU1114

今天广州下雨啦，不过没关系啦，反正我最近也都在刷题学习算法。

昨天做了五题01背包，今天还是背包，不过是完全背包，估计做动态规划要持续好一段时间，一开始选了一道简单题目啦。

HDU1114，看了小一段时间，动手打代码，测调后感觉很NICE，交上去就WA了。

后来，是我的MAX值给得太小了。果断加两个零，马上就A掉了。

完全背包的思路和01背包很相似，就是在循环时候有点不同。

01背包的是：

     memset(dp,0,sizeof(dp));

     memset(v,0,sizeof(v));

     memset(w,0,sizeof(w));

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

       for(j=V;j>=v[i];j--)     //v是volume，w是weight

         dp[j]=max{dp[j],dp[j-v[i]]+w[i] }

完全背包是:

 memset(dp,0,sizeof(dp));

     memset(v,0,sizeof(v));

     memset(w,0,sizeof(w));

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

       for(j=v[i];j<=V;j++)     //循环不同

         dp[j]=max{dp[j],dp[j-v[i]]+w[i] }

这道题要求的是恰好装满了，所以初始要给无穷，dp[0]=0.当然，因为这个是求最坏，所以给的是无穷大。

附上代码

/*******************************************************************************/

/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux

 * Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)

 * Encoding     : UTF8

 * Date         : 2014-03-09

 * All Rights Reserved by yaolong.

*****************************************************************************/

/* Description: complete package*********************************************

*****************************************************************************/

/* Analysis: ******************************************************************

*****************************************************************************/

/*****************************************************************************/

//*

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

#define MAX_N   1000003

int v[MAX_N],w[MAX_N],dp[MAX_N];

int min(int a,int b){

   return a>b?b:a;

}

int main(){

   // freopen("in.txt","r",stdin);

    int cases,E,F,N,i,j,W;

    cin>>cases;

    while(cases--){

        cin>>E>>F;

        cin>>N;

        W=F-E;

        memset(v,0,sizeof(v));

        memset(w,0,sizeof(w));

        for(i=1;i<=W;i++){

            dp[i]=MAX_N;

        }

        dp[0]=0;

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

          cin>>v[i]>>w[i];

        }

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

            for(j=w[i];j<=W;j++){

               dp[j]=min(dp[j],dp[j-w[i]]+v[i]);

            }

            if(dp[W]!=MAX_N){

                cout<<"The minimum amount of money in the piggy-bank is "<<dp[W]<<"."<<endl;

            }else{

                cout<<"This is impossible."<<endl;

            }

    }

   // fclose(stdin);

     return 0;

}