HDU1114BUCU5971——存钱罐——题解

传送门

• • 存钱罐
  • • 题目描述
    • 输入描述
    • 输出描述
    • 样例一
    • • 输入
      • 输出
• 题目分析
• 解题思路
• AC代码

存钱罐

• 存钱罐(航电OJ挂掉了惹)

时间限制：1秒
空间限制：256M

题目描述

存钱罐有个大问题，不打碎存钱罐就无法确定里面有多少钱。

所以可能互出现把存钱罐打碎后发现钱不够的情况。唯一的可能是，称一下存钱罐的重量，试着猜里面有多少钱。

已知存钱罐的重量和每种面值的硬币的重量，请确定存钱罐内的最小金额。

输入描述

第一行包含一个正整数$T$，表示测试用例的数量。

对于每个测试用例：

第一行都包含两个正整数$e$和$f(1\le e\le f\le 10000)$，分别表示存钱罐和装满硬币的存钱罐的重量(单位：克)。

第二行包含一个整数$n(1\le n\le 500)$，表示硬币的总数量。

接下来$n$行，每行都包含两个整数$p$和$w(1\le p\le 50000,1\le w\le 10000)$，分别表示硬币的面值和重量。

输出描述

对于每个测试用例，都输出一行，包含The Minimum amount is x.，其中x是存钱罐内的最小金额。

若无法确定，则输出Impossible...

样例一

输入

3
10 110
2
1 1
30 50
10 110
2
1 1
30 30
1 6
2
10 3
20 4

输出

The Minimum amount is 60.
The Minimum amount is 100.
Impossible...

题目分析

这是一道完全背包

解题思路

完全背包，对每种硬币的数量没有限制。求解在重量不超过$f-e$的情况下存钱罐内的最小金额。

状态表示：$dp[j]$表示重量位$j$的存钱罐内的最小金额。
状态转移方程： $dp[j]=mindp[j],dp[j-w[i]]+val[i]$

AC代码

#include 
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;int dp[50010]; // dp[j]：重量为j的存钱罐内的最小金额
int val[50010]; // 硬币面值
int w[50010]; // 硬币重量int main() {int N;cin >> N;while (N--) {int e, f;scanf("%d%d", &e, &f);int W = f - e;int n;cd(n);for (int i = 0; i < n; i++)cd(val[i]), cd(w[i]); // scanfmemset(dp, 0x3f, sizeof(dp)); // memsetdp[0] = 0;for (int i = 0; i < n; i++)for (int j = w[i]; j <= W; j++)dp[j] = min(dp[j], dp[j - w[i]] + val[i]);if (dp[W] < 1e7)printf("The Minimum amount is %d.\n",dp[W]);elseputs("Impossible...");}return 0;
}

原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/122630623

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！