The backpack problem


Plus
Pin


Problem description Progress
ID 33650. Homer Simpson
Темы: The backpack problem   

Homer Simpson's lunch break is T milliseconds. Homer eats one hamburger in N milliseconds, one cheeseburger in M. How many hamburgers and cheeseburgers should be eaten so that the time spent is as large as possible without exceeding T. If the time spent is equal, it is necessary to maximize the total number of hamburgers and cheeseburgers eaten.

Limits: 1 <=M, N, T, <= 1000000 , all integers.

Input
The first line contains three numbers - M, N and T, separated by spaces.

Imprint
Output the maximum total number of hamburgers and cheeseburgers. If there is some time left, you need to specify it separated by a space. The preferred option is when there is as little extra time left as possible.
 

Input Output
1 2 1000 1000
2 1 1000 1000
3 6 1000 333 1

ID 33086. 0-1 backpack: highest weight
Темы: The backpack problem   

Given N gold bars of mass m1, …, mN. They fill a backpack that can withstand a weight of no more than M. What is the largest amount of gold that can be carried in such a backpack?
 
Input: 
- the first line contains a natural number N not exceeding 100 and a natural number M not exceeding 10000;
- the second line contains N natural numbers mi not exceeding 100.
 
Output: print one integer - the largest possible amount of gold that can be carried in the given backpack.
 

 

Examples
# Input Output
1
2 3195
38 41
 79

ID 33087. 0-1 backpack: minimum items
Темы: The backpack problem   

Given N items of mass m1, …, mN. They fill a backpack that can withstand a weight of no more than M. How to gain weight in exactly M using as few items as possible?
 
Input:
- the first line contains a natural number N not exceeding 100 and a natural number M not exceeding 10000;
- the second line contains N natural numbers mi not exceeding 100.
 
Output: Print the smallest number of items you need, or 0 if you can't gain the given weight.
 

 

Examples
# Input Output
1
1 5968
18
 0

ID 33081. Knapsack problem with answer recovery
Темы: The backpack problem   

Given N items of mass m1, …, mN and cost c< sub>1, …, cN respectively. 
They fill a backpack that can withstand a weight of no more than M. Determine the set of items that can be carried in a backpack that has the highest cost.
 
Input: 
- the first line contains a natural number N not exceeding 100 and a natural number M not exceeding 10000;
- on the second line enter N natural numbers mi not exceeding 100;
- N natural numbers withi not exceeding 100 are entered in the third line.
 
Output: print the numbers of items (numbers from 1 to N) that will be included in the backpack of the highest cost (one number per line).
 

 

Examples
# Input Output
1
4 6
2 4 1 2
7 2 5 1
 1
3
4

ID 33105. Money box
Темы: The backpack problem   

The weight E of an empty piggy bank and the weight F of a piggy bank with coins are set. The piggy bank can contain coins of N types, for each type the value Pi and the weight Wi are known one coin. Find the minimum and maximum amount of money that can be in the piggy bank.

Input: 
- the first line contains numbers E and F (\(1<=E<=F<=10000\)< /span>);
- in the second - number N (\(1<=N<=500\));
- in the next N lines - two numbers each, Pi and Wi (\(1<=Pi<=50000\), \(1<=Wi<=10000\) ).
All numbers are integers.

Output: two numbers separated by a space are displayed - the minimum and maximum sums. If the piggy bank cannot have exactly the specified weight, provided that it is filled with coins of the specified types, print "This is impossible.".

 
 

 

Examples
# Input Output
1
1000 1100
2
1 1
5 2
 100 250
2
1000 1010
2
6 3
2 2
 10 16
3
1000 2000
1
10 3
 This is impossible.

ID 33088. Weights
Темы: The backpack problem   

Given a set of weights m­1, …, mN. Can they be divided into two scales so that they are in balance?
 
Input:
- the first line contains a natural number N, not exceeding 100;
- the second line contains N natural numbers mi not exceeding 100.
 
Output: output YES or NO.
 

 

Examples
# Input Output
1 1
17		 NO
2 2
19 19 		YES

ID 33104. Surrender - 1
Темы: The backpack problem   

The buyer wants to purchase a product worth S rubles. He has N banknotes in denominations of P1, P2, ..., PN< /code> rubles. The seller has M banknotes in denominations of Q1, Q2, ..., QM< /code>. rubles. Determine if they can pay.
 
Input: 
- the first line sets the sum S;
- in the second line - number N;
- in the third line  - N numbers P1, P2, ..., PN ;
- in the fourth line - number M;
- in the fifth line - M numbers Q1, Q2, ..., QM.
The number of banknotes from the seller and the buyer and their denominations do not exceed 100.
 
Output: if the seller can pay the buyer, print the denominations of banknotes that the buyer gives to the seller and which he receives as change. Print the number with the “+” sign if the buyer gives the banknote of the corresponding denomination to the seller and with the “-” sign if the buyer receives this banknote for change. Separate denominations of banknotes with a space.
If they can't pay, print the string Impossible.
 

 

Examples
# Input Output
1
10
3
3 9 14
2
6 2
 -2 +9 +3
2
100
3
74 35 8
2
196
 Impossible

ID 38366. Again chestnuts
Темы: The backpack problem   

In this problem, as in problem B, Petya takes his M-pawed Beast for a walk again (however, the number of paws the Beast can have up to 1000 in this problem). Again, his mother left him N pants with respectively K1, K2, …, KN pants. However, grouse Petya wants to put pants on the Beast so that the following conditions are met:

  • Each paw was wearing at least one trouser leg (guaranteed that this is always possible),
  • number of pants worn on the most "insulated" paw should differ as little as possible from the number of pants worn on the lightest paw (when the number of pants worn on different paws is very different, the Beast feels discomfort),
  • Unlike task B, Petya is not obliged to put on the Beast all available pants — some of them can be left at home.
As before, any pants can be worn on any set of paws. In particular, you can't wear multiple legs of the same pants on the same Beast's paw.

Help Petya – write a program that for each paw will indicate how many pants should be worn on it.

Input
The number M is entered first, and then the number N (1 ≤ M ≤ 1000, 1 ≤ N ≤ 100). Next, N numbers Ki are entered, denoting the number of pants for the pants left by the mother (1 ≤ Ki ≤ M). The sum of all Ki is not less than M.

Imprint
Print M lines, the i-th line should contain the number of pants worn on the i-th paw. If there are several answers you are looking for, then print any of them.
 
Examples
# Input Output Explanation
1 4 3
1 2 3 		1
1
1
1		 First pants worn on paw 1;
we do not use second pants;
the third pants are worn on paws 2, 3 and 4.
Thus, on all paws 1 pant.
2 4 2
3 2		 2
1
1
1		 First pants worn on legs 1, 2 and 3;
the second pants are worn on legs 1 and 4.
Thus, the number of pants on the most "insulated" paw (this is paw number 1) – 2, and on the remaining paws, one leg each, i.e. the number of trousers on different paws differs by one. It is easy to see that in this example it is impossible to dress the animal in such a way that all legs have equal trouser legs, so this answer is optimal.