PROBLEM DESCRIPTION

A battalion is a military unit with 300 to 1200 soldiers usually consisting of seven companies commanded either by a lieutenant colonel or a colonel.

A particular training that a battalion undergoes is the training to maximize the battalion's "carrying capacity" whenever they are to carry cargoes from point A to point B. This usually happens when convoys full of supplies, guns, and ammunition are delivered and they have to put it away into a safehouse by foot.

The premise: Each soldier has a maximum carrying capacity (often in Kilograms). Most of the time, this is engraved into his official dog-tag for the colonel's reference. The command is to carry only one cargo per soldier. A scenario where two or more soldiers are carrying a single cargo, when it is still possible for them to carry one each, is considered to be inefficient (Tracy, 2008 - Principle of Forced Efficiency).

For this particular problem, assume that the number of soldiers per test case always equal that of the number of cargoes.

INPUT FORMAT (INPUT FILE: cp01.in)

The input file begins with an integer T, 0 < T ≤ 100, which defines the number of test cases. Each test case consists of 3 lines. The first line contains an integer N, where 0 < N ≤ 1200, that specifies the number of cargoes. The second and third lines each contain exactlyNpositive integers whose values do not exceed100. The integers on the second line are the weights of the cargoes and the integers on the third line are the weight limits both in kilograms.

OUTPUT FORMAT (OUTPUT FILE: cp01.out)

For each test case, output the maximum number of cargoes that the selected soldiers from the battalion can carry in one wave if they are restricted to carry only one cargo per soldier.

SAMPLE INPUT

2
3
10 30 20
30 10 20
5
9 7 16 4 8
8 3 14 10 10

SAMPLE OUTPUT

3
4

what would be the code to output 3 4 from the input above?help pls.

Edited 3 Years Ago by azurekite

Do you know how to actually solve this, and you just don't know how to code it, or do you have no idea how to solve this?

Edited 3 Years Ago by Moschops

the only think that i know is that we may use Knapsack Problem,loops ,sort,array or vector in trying to solve this.sorry, I was only a beginner in c++ prog.

The difficultly here is not really in coding it. It's in understanding the problem. Start by doing it on paper. Here's the question, without all the things that are added to make it harder to understand.

You will be given two lists of numbers. The lists will be the same size. You must create as many number pairs as possible; each pair is one number from the first list, and one number from the second list. The rules for pairing them are as follows; the number from the second list must be the same as, or higher than, the number from the first list. The answer we want is how many pairs you made.

Here is an example:
1st list: 9 7 16 4 8
2nd list: 8 3 14 10 10

Pairings: 14-9 10-8 10-7 8-4

There is no way to make more than four pairings, so the answer is four. Why didn't we include the 16 from the first list in one of the pairings? Because there is no number on the second list the same or larger.

Now that the question is clear, work out a way to do it on paper. The algorithm is quite simple.

This is programming, by the way; thinking about a problem in a way that the solution lends itself to a programmatic implementation. All the rest is just memorising syntax and learning what the tools are for.

Edited 3 Years Ago by Moschops

This question has already been answered. Start a new discussion instead.