HDU 1114（完全背包）

本文主要是介绍HDU 1114（完全背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

 

#include <cstring>
#include <cstdio>
int cost[509], weight[509];
int dp[10009];
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define INF 25000009
int main()
{
int T, E, F, N, i, j, V;
scanf("%d", &T);
while (T--)
{
scanf("%d%d%d", &E, &F, &N);
for (i = 0; i < N; ++i)
scanf("%d%d", weight+i, cost+i);
V = F - E;
//memset(dp+1, -1, sizeof(int) * V);
dp[0] = 0;
for (i = 1; i <= V; ++i) dp[i] = INF;
for (i = 0; i < N; ++i)
for (j = cost[i]; j <= V; ++j)
dp[j] = MIN(dp[j], dp[j-cost[i]] + weight[i]);
if (dp[V] == INF)
printf("This is impossible.\n");
else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[V]);
}
return 0;
}

 

这篇关于HDU 1114（完全背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---