HDU 1114（完全背包）

╰+攻爆jí腚メ 2022-09-20 11:17 283阅读 0赞

题意：给出小猪钱罐空时的重量E，满时的重量F，钱币的种类N，接下来N行，分别为p w，p为钱币价值，w为钱币重量，求钱罐中钱币的最小价值。

  1. #include <cstring>
  2. #include <cstdio>
  4. int cost[509], weight[509];
  5. int dp[10009];
  6. #define MIN(a, b) ((a) > (b) ? (b) : (a))
  7. #define INF 25000009
  8. int main()
  9. {
  10.     int T, E, F, N, i, j, V;
  11.     scanf("%d", &T);
  12.     while (T--)
  13.     {
  14.         scanf("%d%d%d", &E, &F, &N);
  15.         for (i = 0; i < N; ++i)
  16.             scanf("%d%d", weight+i, cost+i);
  17.         V = F - E;
  18.         //memset(dp+1, -1, sizeof(int) * V);
  19.         dp[0] = 0;
  20.         for (i = 1; i <= V; ++i) dp[i] = INF;
  21.         for (i = 0; i < N; ++i)
  22.             for (j = cost[i]; j <= V; ++j)
  23.                 dp[j] = MIN(dp[j], dp[j-cost[i]] + weight[i]);
  24.         if (dp[V] == INF)
  25.             printf("This is impossible.\n");
  26.         else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[V]);
  27.     }
  28.     return 0;
  29. }

发表评论

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

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

相关阅读

    相关 HDU 1171(完全背包)

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

    蔚落蔚落/ 0 赞/ 259 阅读