|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 |
Piggy-BankTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 9526 Accepted Submission(s): 4803Problem DescriptionBefore ACM can do
anything, a budget must be prepared and the necessary financial support obtained. The main income for
this action comes from
Irreversibly Bound Money (IBM). The idea behind is
simple. Whenever some ACM member has any small money, he takes all the coins and throws them into
a piggy-bank. You know that this
process is
irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long
time, there should be enough cash in
the piggy-bank to pay everything that needs to be paid. But there is
a big problem with piggy-banks. It is
not possible to determine how much money is
inside. So we might break
the pig into
pieces only to find out
that there is
not enough money. Clearly, we want to avoid this
unpleasant situation. The only possibility is
to weigh the piggy-bank and try
to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is
some minimum amount of money in
the piggy-bank that we can guarantee. Your task is
to find out
this worst case
and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs! InputThe input consists of T test cases. The number of them (T) is
given on
the first line of the input file. Each test case
begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in
grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is
an integer number N (1 <= N <= 500) that gives the number of various coins used in
the given currency. Following this
are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is
the value of the coin in
monetary units, W is
it‘s weight in
grams. OutputPrint exactly one line of output for
each test case. The line must contain the sentence "The minimum amount of money in the piggy-bank is X."
where X is
the minimum amount of money that can be achieved using
coins with the given total weight. If the weight cannot be reached exactly, print a line "This is impossible.". Sample Input310 11021 130 5010 11021 150 301 6210 320 4 Sample OutputThe minimum amount of money in
the piggy-bank is
60.The minimum amount of money in
the piggy-bank is
100.This is
impossible. |
大意：存钱罐空时重E，满时重F；有N种硬币，价值为P，重量为W；求是否满足恰好装满时有最小价值的储蓄。
#include<iostream> #include<algorithm> #include<string> #define MAX_N 502 #define MAX_W 10002 #define INF (1 << 20) using namespace std; int dp[MAX_W], w[MAX_N], v[MAX_N]; int W; int main() { int T, E, F, N; cin >> T; while (T--){ cin >> E >> F; W = F - E; cin >> N; for (int i = 0; i < N; i++){ cin >> v[i] >> w[i]; } dp[0] = 0; for (int i = 1; i <= W; i++){ dp[i] = INF; } for (int i = 0; i < N; i++){ for (int j = w[i]; j <= W; j++){ dp[j] = min(dp[j], dp[j - w[i]] + v[i]); } } if (dp[W] < INF){ cout << "The minimum amount of money in the piggy-bank is " << dp[W] <<"."<< endl; } else{ cout << "This is impossible." << endl; } } system("pause"); return 0; }
原文：http://www.cnblogs.com/littlehoom/p/3550906.html