hdu 题目1114 Piggy-Bank（完全背包）

た 入场券 2022-09-18 12:44 129阅读 0赞

http://acm.hdu.edu.cn/showproblem.php?pid=1114

完全背包

  1. /***************************
  2. #  2013-11-22 13:20:22 
  3. # Time: MS   Memory: K
  4. # Author: zyh
  5. ***************************/ 
  7. #include<iostream>
  8. #include<algorithm>
  9. #include<stdio.h>
  10. #include<string.h>
  11. #include<stdlib.h>
  12. #include<math.h>
  13. using namespace std;
  14. const int INF = 99999999; 
  15. int n,f[10005],c[505],w[505]; 
  16. int completepack(int V)
  17. {
  18.     int i,v;    
  19.     for(f[0]=0,i=1;i<=V;i++) f[i]=INF; 
  20.     for(i=0;i<n;i++){
  21.         for(v=c[i];v<=V;v++){
  22.             if(f[v]>f[v-c[i]] +w[i] )
  23.                 f[v] = f[v-c[i]]+w[i];
  24.         }
  25.     } 
  26.     return f[V];
  27. } 
  29. int main()
  30. {
  31.     int t,i,a,b,ans,flag;
  32.     scanf("%d",&t);
  33.     while(t--){
  34.         scanf("%d%d",&a,&b);
  35.         b = b - a;
  36.         scanf("%d",&n);
  37.         for(i=0;i<n;i++) scanf("%d%d",&w[i],&c[i]);
  38.         ans = completepack(b);
  39.         if(ans==INF) puts("This is impossible.");
  40.         else printf("The minimum amount of money in the piggy-bank is %d.\n",ans);
  41.     }
  42.     return 0; 
  43. }

发表评论

表情：
评论列表 （有 0 条评论，129人围观）

还没有评论，来说两句吧...

相关阅读

    相关 HDU 1171(完全背包)

    题意：给一个数n，接下来n行，每行对应一个设备的两个值，第一个为设备的价值，第二个为该设备的数量。如何把所有设备一分为二，求两部分的价值总和尽量接近。   incl

    蔚落蔚落/ 0 赞/ 259 阅读