|
Problem Description
Before 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.（问题描述；在ACM可以做任何事情之前，必须编制预算并获得必要的财务支持。这一行动的主要收入来自不可逆绑定货币(IBM)。背后的想法很简单。每当某个ACM成员有小钱时，他就会把所有的硬币都扔进存钱罐。你知道这个过程是不可逆的，不打碎猪就不能取出硬币。足够长的时间后，储钱罐里应该有足够的现金来支付所有需要支付的费用。）
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!（但是存钱罐有一个大问题。无法确定里面有多少钱。所以我们可能会把猪撕成碎片，却发现没有足够的钱。显然，我们想避免这种不愉快的情况。唯一的可能是称一下存钱罐，试着猜猜里面有多少硬币。假设我们能够准确地确定猪的重量，并且我们知道给定货币的所有硬币的重量。然后存钱罐里有一些我们可以保证的最低金额。你的任务是找出最糟糕的情况，并确定存钱罐中的最小现金量。我们需要你的帮助。再也没有过早破碎的猪了！）
Input
The 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.（Input
The 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.
Input
The 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.（输入 ；由测试用例组成。它们的数量(T)在输入文件的第一行给出。每个测试用例以一行包含两个整数E和f开始。它们表示空的猪和装满硬币的猪的重量。两种重量都以克为单位。没有猪的体重会超过10公斤，也就是说1 <= E <= F <= 10000。在每个测试用例的第二行，有一个整数N (1 <= N <= 500)，给出给定货币中使用的各种硬币的数量。紧随其后的是N行，每一行指定一种硬币类型。这两行各包含两个整数，Pand W (1 <= P <= 50000，1 <= W <=10000)。p是以货币单位表示的硬币价值，W是以克表示的重量。。）
Output
Print 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.”.（输出；为每个测试用例精确地打印一行输出。该行必须包含句子“存钱罐中的最小金额为X”，其中X是使用给定总重量的硬币可以获得的最小金额。如果不能准确达到重量，打印一行“这是不可能的。”。）
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
int dp[10005]; || 定义一个数组为存钱猪。
int v[10005]; ||v为硬币的币值。
int w[10005]; || w为硬币的质量。
int main()
{
int t; || 定义总共需要t个测试。
scanf("%d",&t);
while(t--) || 每测试一次次数减一。
{
int e,f,n,a; || 定义a为硬币的总质量，f为满猪的质量，e为空猪的质量，n为硬币的种类。
scanf("%d%d",&e,&f);
scanf("%d",&n); || 输入e，f，n。
for(int i=0; i<n; i++) || 定义从第一个硬币开始循环探索
{
scanf("%d%d",&v[i],&w[i]); || 记录此硬币的币值，质量。
}
a=f-e; || 满猪的质量减去空猪的质量等于硬币的总质量。
for(int i=1; i<=a; i++)
{
dp[i]=10000000; || 定义数组重量为这个范围内的最大值，以方便找到单位最小的硬币。
}
dp[0]=0; || 数组为零时，硬币钱数为零。
for(int i=0; i<n; i++) ||定义i从第一个开始循环探索
{
for(int j=w[i]; j<=a; j++) || 重新定义一个j为现在这个硬币的质量，若这个硬币的质量小于a，则继续循环。
{
dp[j]=min(dp[j],dp[j-w[i]]+v[i]); || 第j个和i个的质量相等，取硬币币值小的那个。
}
}
if(dp[a]<10000000) || 若数组小于最大值，则有情况把存钱猪装到相应硬币币值的重量。
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[a]);
}
else || 反之则没有。
{
printf("This is impossible.\n");
}
}
return 0;
}
这道题给出了硬币的类型，也就是说存钱猪里有多种硬币，这就需要比较硬币的重量和硬币的币值了，以找到最小值，然后根据质量确定满猪时候的最小金额。
|