小白算法练习 简单背包专题003 完全背包 hdu lanqiao 包子凑数 dp

Piggy-Bank

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 27151    Accepted Submission(s): 13745

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<algorithm>
using namespace std; int main(){ int T;
    cin>>T; while(T--) { int w1,w2; int w;
        cin>>w1>>w2;
        w=w2-w1; int N;
        cin>>N; int v[10008]; int c[10008]; int dp[100008]; for(int i=0;i<=w;i++){
            dp[i]=10000008; } for(int i=0;i<N;i++) {
            cin>>v[i]>>c[i]; }    
        dp[0]=0; for(int i=0;i<N;i++) { for(int j=c[i];j<=w;j++) {
                dp[j]=min(dp[j],dp[j-c[i]]+v[i]); } } if(dp[w] == 10000008 )      
            printf("This is impossible.\n"); else  
            printf("The minimum amount of money in the piggy-bank is %d.\n",dp[w]); } return 0; }

 

   

标题：包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入
----
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)  

输出
----
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。

例如，
输入：
2  
4  
5   

程序应该输出：
6  

再例如，
输入：
2  
4  
6    

程序应该输出：
INF

  

#include<iostream>
using namespace std;
const int Max=100008;
bool dp[Max];
int gcd(int a,int b){
	if(b==0)
	{
		return a;
	}
	return gcd(b,a%b);
}
int main(){
	int N;
	cin>>N;
	int arr[108];
	for(int i=0;i<N;i++)
	{
		cin>>arr[i];
	}
	int _gcd=arr[0];
	for(int i=1;i<N;i++)
	{
		_gcd=gcd(_gcd,arr[i]);
	}
	if(_gcd!=1)
	{
		cout<<"INF"<<endl;
	}
	else
	{	
	dp[0]=true;  //初始化状态是必要的
        for(int i=0; i<N; i++)  
            for(int j=0; j<=Max; j++)  
            {  
                if(dp[j])  //由于dp存放的是 已有i种类型的包子，是否能平成j的需求，所以假如能满足j那么j+arr[i]件包子也满足要求
                {  
                    dp[j+arr[i]]=true;  
                }  
            }  
        int count=0;  
        for(int i=0; i<=Max; i++)  
            if(dp[i]==false) count++;  
        printf("%d\n",count);  
	}
}

Lucky Sum of Digits

Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya wonders eagerly what minimum lucky number has the sum of digits equal to n. Help him cope with the task.

Input

The single line contains an integer n (1 ≤ n ≤ 106) — the sum of digits of the required lucky number.

Output

Print on the single line the result — the minimum lucky number, whose sum of digits equals n. If such number does not exist, print -1.

Sample test(s)

input

11

output

47

input

10

output

-1

#include<iostream>
using namespace std;
bool dp[1000008];

int main(){
	int n;
	cin>>n;
	int v[2]={4,7};
	dp[0]=1;	
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<=1000008;j++)
		{
			if(dp[j])
			{
				dp[j+v[i]]=1;
			}
		}
	}
	if(dp[n]==0){
		cout<<-1<<endl;
	}
	else
	{
		for(;n%7!=0;n=n-4)
		{
			cout<<4;
		}
		for(;n!=0;n=n-7)
		{
			cout<<7;
		} 
		cout<<endl;
	}
}