Combination Algorithm Help

Question

2.00/5 (1 vote)

See more:

So, I'm creating a combination algorithm. Here are the challenge details: You need to create a program to accept 4 integer inputs, representing points associated with how much a fish is worth (first three integer inputs representing three different fish) and then see how many combinations can fit into the total amount (last integer input representing the total amount of fish points you can have).

The input would be like this in a console program,
1 // fish point value
2 // fish 2 point value
3 // fish 3 point value
2 // total amount of points somebody can have without exceeding the limit

The output would be displayed like this,
1 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
2 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
0 Brown Trout, 1 Northern Pike, 0 Yellow Pickerel
Number of ways to catch fish: 3

I've been given some tips like using loops inside of loops and to use a while loop, but I'm still pretty new and confused. Any tips or maybe some sample code that would make this program happen?

Posted 19-Oct-15 12:30pm

Member 12071339

Add a Solution

Comments

Sergey Alexandrovich Kryukov 19-Oct-15 18:57pm

Rephrasing the known joke, "how to tell a mathematician from non-mathematician", I would note: a mathematician would first list the solution [0, 0, 0], but you only listed solution with at least one non-null number of fish. Therefore, the whole solution will be this: start developing mathematician's skills. :-)
The problem is not about the loops at all, it's about developing the algorithm and perhaps developing a more efficient algorithm, because brute-force one seems quite obvious...
—SA

Patrice T 19-Oct-15 20:55pm

++ :)

BillWoodruff 20-Oct-15 8:54am

What makes this problem more than trivial is the possibility you have a relatively large point-limit, and, within that limit, for example, you could have a maximum of 4 perch, 3 trout, 2 pickerel. For every possible value of each of the three variables, you will have to consider the combinations of all the other variables.

That means for each possible number of perch 1~4 you have to find all combinations of trout and pickerel that could possibly "fit" in the point-limit.

Patrice T 20-Oct-15 14:45pm

What have you done ?
The problem look intimidating, but is rather easy.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Accepted Answer · 2015-10-19T13:32:00

I just realized that this is very similar to the well-known Knapsack problem, only you don't need to find the optimal solution, just need to list them all: https://en.wikipedia.org/wiki/Knapsack_problem[^].

From this article, you can find the overview of known solutions. Not all of them will be helpful for you, because you need to list all solutions not exceeding the maximum total value, not the best one. Anyway, as the problem is found to be NP-complete (https://en.wikipedia.org/wiki/NP-completeness[^]), you have nothing to do but try all possible solutions, so you just need to list them.

Let's call the "solution" the set of numbers representing the number of caught fish of each species. So, you need to fill in the array of integers representing the number of caught fish with numbers 0 to N and choose only the solution with total point amount not exceeding the allowed maximum for total amount.

First, I would find the maximum numbers of caught fish of each species, not exceeding the maximum total amount in the case you catch fish of only this species. Having N species i = 1... N, your maximum fish numbers for each species will be inside the ranges

species₀: [ 0.. Max_species₀ ]
species₁: [ 0.. Max_species₁ ]
...
species_N-1: [ 0.. Max_{species_N−1} ]

The total number of variants to check up won't exceed the number

(Max_species₀+1) * (Max_species₁+1) *... (Max_{species_N−1}+1).

You can try all those combinations in some order, that's it.

—SA