HDU 1114 Piggy-Bank 全然背包[通俗易懂]

HDU 1114 Piggy-Bank 全然背包

大家好,又见面了,我是全栈君。

Piggy-Bank

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

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>
const int INF = 1e7;
using namespace std;
int dp[1000005],v[600],p[600];
int max(int x,int y)
{
    if(x > y)
        return x;
        else
    return y;
}
int min(int x,int y)
{
    if(x > y)
        return y;
        else
    return x;
}
int main()
{
   int T,VM,Vz,n;
   scanf("%d",&T);
   while(T--)
   {
       scanf("%d%d",&Vz,&VM);
       scanf("%d",&n);
       int st = VM - Vz;
       for(int i = 0;i<=st;i++)
        dp[i] = INF;
        dp[0] = 0;
       for(int i = 1;i<=n;i++) scanf("%d%d",&p[i],&v[i]);
       for(int i = 1;i<=n;i++)
       {
           for(int j = v[i];j<=st;j++)
           {
               dp[j] = min(dp[j-v[i]]+p[i],dp[j]);
           }
       }
       if(dp[st]>=INF)
        puts("This is impossible.");
        else
       printf("The minimum amount of money in the piggy-bank is %d.\n",dp[st]);

    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116618.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 京东自助代挂_京东任务代挂

    京东自助代挂_京东任务代挂京东自动签到-代挂效果展示说明效果展示说明JD签到网站:点我进入京东签到网站    JD签到,东东农场等活动自动帮做,每天都会自动浇水。每天都有200-1000豆豆不等入账,相当于坐等收钱,JD只要出了新活动网站都会同步更新,不需要担心任何活动,每天都会帮你自动完成。…

  • 聚集索引和非聚集索引的区别[通俗易懂]

    聚集索引和非聚集索引的区别[通俗易懂]一、深入浅出理解索引结构实际上,可以把索引理解为一种特殊的目录。微软的SQLSERVER提供了两种索引:聚集索引(clusteredindex,也称聚类索引、簇集索引)和非聚集索引(nonclusteredindex,也称非聚类索引、非簇集索引)。下面,我们举例来说明一下聚集索引和非聚集索引的区别:其实,我们的汉语字典的正文本身就是一个聚集索引。比如,我们要查“安”字,因为“安”的拼音是…

  • @component使用案例

    @component使用案例

  • eclipse导入Maven工程层级显示修改方法

    eclipse导入Maven工程层级显示修改方法最近换项目,在导入maven工程的时候发现导入显示的层级关系很不清楚,看的很不习惯,纠结半天之后发现应该如何处理。选择该项后会看到有两个选择,Flat和Hierarchical两个选择,这两个选项的意思分别是平铺与层级显示。将Flat改为Hierarchical即可。这时就变成层级显示了…

  • python画图时给图中的点加标签之plt.text

    python画图时给图中的点加标签之plt.textplt.text给图中加标签

  • 软件工程实验报告:图书管理系统

    软件工程实验报告:图书管理系统一、课程设计的目的与要求课程设计目的软件工程课程设计是学习软件工程课程后所进行的实践环节,目的是培养学生用工程化的思想和标准文档化的思想进行软件开发。本次课程设计通过开发一个小型实用的软件系统,亲身体验软件生命周期中的各个环节,以加深对软件工程课程的深入理解、锻炼独立分析、解决问题的能力。课程设计要求2.1课程设计准备1)复习软件工程课程的主要内容,熟练掌握软件生命周期的理论以及各阶段的基本概念。2)明确可行性分析、需求分析、设计、测试等阶段的基本任务和基本方法。3)熟练运用规范化的描述

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号