HDU 1114 (dp 完全背包)

鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1114

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.

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.

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.".

Sample Input

3

10 110

2

1 1

30 50

10 110

2

1 1

50 30

1 6

2

10 3

20 4

Sample Output

The minimum amount of money in the piggy-bank is 60.

The minimum amount of money in the piggy-bank is 100.

This is impossible.

代碼如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 10005
#define INF 10000000
using namespace std;

int cas;
int dp[MAXN];
int Empty_Weight, Total_Weight, Rest_Weight;
int Coin_Value, Coin_Weight, Coin_Type;

int Min(int x, int y) { return x < y ? x : y; }

int main()
{
    scanf("%d", &cas);
    while(cas--) {
        scanf("%d %d %d", &Empty_Weight, &Total_Weight, &Coin_Type);
        for(int i=0; i<MAXN; i++) dp[i] = INF;
        dp[0] = 0;
        Rest_Weight = Total_Weight - Empty_Weight;
        for(int i=0; i<Coin_Type; i++) {
            scanf("%d %d", &Coin_Value, &Coin_Weight);
            for(int j=Coin_Weight; j<=Rest_Weight; j++) {
                dp[j] = Min(dp[j], dp[j-Coin_Weight]+Coin_Value);
            }
        }
        if(dp[Rest_Weight] < INF) printf("The minimum amount of money in the piggy-bank is %d.\n", dp[Rest_Weight]);
        else puts("This is impossible.");
    }
    return 0;
}
时间: 09-01

HDU 1114 (dp 完全背包)的相关文章

HDU 1114 Piggy-Bank(一维背包)

题目地址:HDU 1114 把dp[0]初始化为0,其它的初始化为INF.这样就能保证最后的结果一定是满的,即一定是从0慢慢的加上来的. 代码例如以下: #include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #incl

hdu 1114 Piggy-Bank 完全背包

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1114 题意分析:给出存钱罐存钱前后的重量,以及钱的种类及其价值和种类, 要求装满存钱罐最小的价值.  完全背包 /*Piggy-Bank Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13578 Accepted Submission(s):

hdu 1114 基础完全背包

题意:给一个储钱罐,已知空的储钱罐和装了硬币的储钱罐的质量.然后给了n种硬币的质量和价值. 问储钱罐里最少有多少钱. 解法:完全背包.注意要初始化为 INF,要正好装满,如果结果是INF,输出This is impossible. 1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #includ

HDU 1114 Piggy-Bank 全然背包

Piggy-Bank Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Description Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action come

hdu 1171 Big Event in HDU(dp 01背包 母函数)

01背包 #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> using namespace std; int v[100],m[100]; int dp[300000]; int main() { int n; int i,j,k; while(scanf("%d",&n)!=EOF) {

hdu 5312 dp(背包)、二分图或其他姿势

题意:给出一个二分图(不一定连通),问最多能加多少边,使它仍然是二分图 BC周年庆第四题,貌似终判再终判之后数据还是有问题``` 据说貌似可以用bitset搞,而且姿势优美是正解```然而我还是用的dp过的 首先就是用黑白染色判断每个区块的两边点的个数,接着因为要边数最多,所以显然要两边点数尽量接近,所以我就用01背包的方法,计算能够得到的 n/2 内的半边最大点数,中间加入已达到的最大值优化和黑白染色得到单点额外记录而不进入背包的优化```然后从TLE变成了200+ms过,只能说出数据的太执着

hdu 1561The more, The Better(树形dp&amp;01背包)

The more, The Better Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4949    Accepted Submission(s): 2918 Problem Description ACboy很喜欢玩一种战略游戏,在一个地图上,有N座城堡,每座城堡都有一定的宝物,在每次游戏中ACboy允许攻克M个城堡并获得里面的宝

[HDU 1114] Piggy-Bank (动态规划)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1114 简单完全背包,不多说. 1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <map> 6 #include <iterator> 7 #include <vector> 8 using

hdu 1114 完全背包问题

题意:给定背包体积与物品的体积与价值 求正好放完的最小价值#include<iostream> using namespace std; int min(int a,int b) { if(a<b) return a; return b; } int main() { int t,m1,m2,n,i,j; int v[502],w[502],dp[10005],m; cin>>t; while(t--) { cin>>m1>>m2; m=m2-m1;

HDU 2955 Robberies --01背包变形

这题有些巧妙,看了别人的题解才知道做的. 因为按常规思路的话,背包容量为浮点数,,不好存储,且不能直接相加,所以换一种思路,将背包容量与价值互换,即令各银行总值为背包容量,逃跑概率(1-P)为价值,即转化为01背包问题. 此时dp[v]表示抢劫到v块钱成功逃跑的概率,概率相乘. 最后从大到小枚举v,找出概率大于逃跑概率的最大v值,即为最大抢劫的金额. 代码: #include <iostream> #include <cstdio> #include <cstring>