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)


相关推荐

  • 如何利用腾讯云服务器搭建个人网站[通俗易懂]

    如何利用腾讯云服务器搭建个人网站[通俗易懂]你是否想要搭建一个网站,却苦苦找不到方法,你是否看到别人搭建的网站,自己羡慕不已,今天,就教大家来搭建一个简单的个人网站。在这里,我采用的是腾讯云服务器搭建的。首先,需要注册腾讯云账号,登录腾讯云,点击控制台进入控制台后,选择域名注册看到的结果如下图所示:开始注册域名:提交订单后,域名就注册成功了。接下来需要购买云主机(云服务器),流程如下用…

  • Django(64)频率认证源码分析与自定义频率认证「建议收藏」

    Django(64)频率认证源码分析与自定义频率认证「建议收藏」前言有时候我们发送手机验证码,会发现1分钟只能发送1次,这是做了频率限制,限制的时间次数,都由开发者自己决定频率认证源码分析defcheck_throttles(self,request):

  • lseek 出错

    lseek 出错学习windows游戏编程大师时,运行加载位图的函数出错intLoad_Bitmap_File(BITMAP_FILE_PTRbitmap,char*filename) 网上搜的答案 其实这个函数之所以失败是因为你使用的编译器问题,如果你使用vc6就没问题,问题是这样的,像OpenFile,_lseek等这样的函数是16位windows时期的文件操作函数,在vc中它的运

  • vscode一键注释_vscode代码缩进快捷键

    vscode一键注释_vscode代码缩进快捷键新建HTML文件时,输入感叹号(!),按tab键,系统没有反应,不会自动补全。新版本用html:5会自动补全

  • 基于单片机的电子时钟设计(keil+protues仿真,含代码及原理图)

    基于单片机的电子时钟设计(keil+protues仿真,含代码及原理图)  本学期单片机课程要求做课程设计,我选取的课题如下:基于单片机的电子时钟设计,要求:(1)实时显示当前时间;(2)能够对时间进行设置;(3)包括年月日,小时,分钟,秒.(4)整点提醒功能.经过一周的时间已实现上述功能,故在此分享一下;所选用器材单片机最小系统(这就不用细说了吧,这里我选用AT89C51),排阻,四个按钮开关,8位共阴数码管,蜂鸣器;prot……

  • mac Intrellij idea 的激活码【2021最新】

    (mac Intrellij idea 的激活码)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

发表回复

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

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