poj 3260 The Fewest Coins

// 转载自
http://blog.163.com/benz_/blog/static/18684203020115721917109/
算法不难看出，就是一个无限背包+多重背包。
问题在于背包的范围。
设John出了X元，则需要找零X-T元。
证明X不超过T+v_max^2：
假设超过了，则找零超过v_max^2，则找零的货币数定超过v_max，
根据抽屉原理，必然有若干个货币组合起来是v_max的倍数，
那么这些货币肯定可以在给钱的时候少给一些，从而推出这样的方案肯定不是最优方案。
复杂度：O(n*(T+vmax^2)) 

// 我自己做时 是把所有 v[i]相加 得到的 复杂度为 O(n*(T+sum{v[i]})) 然后 WA告诉我我的想法是错误的
// 然后试了下 直接让sum =12000 居然A掉了 然后百度了下  找到了上面的证明

#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MOD 1000000007
#define maxn 24410
int dp[maxn];
int dp2[14410];
int V[110];
int sum;
int num[110];
int main()
{
    int N,T;
    while(scanf("%d %d",&N,&T)!=EOF){
      int i,j,k;
      sum=0;
      for(i=1;i<=N;i++)
        scanf("%d",&V[i]),sum=max(sum,V[i]);//,sum+=V[i];
      for(i=1;i<=N;i++)
        scanf("%d",&num[i]);
    sum=sum*sum;
       for(i=1;i<=T+sum;i++)
         dp[i]=MOD;
       for(i=1;i<=sum;i++)
         dp2[i]=MOD;

      for(i=1;i<=N;i++){
          k=1;
          int tp;
          while(num[i]>=k){
            tp=k*V[i];
            for(j=sum+T;j>=tp;j--)
                dp[j]=min(dp[j],dp[j-tp]+k);
            num[i]-=k;
            k=k<<1;
          }
          if(num[i]){
             k=num[i];
             tp=k*V[i];
            for(j=sum+T;j>=tp;j--)
                dp[j]=min(dp[j],dp[j-tp]+k);
          }

         for(j=V[i];j<=sum;j++)
             dp2[j]=min(dp2[j],dp2[j-V[i]]+1);
      }
      int ans=MOD;
      for(i=T;i<=sum+T;i++)
        ans=min(ans,dp[i]+dp2[i-T]);
      if(ans==MOD) printf("-1
");
      else printf("%d
",ans);
    }
    return 0;
}