Click here to Skip to main content
15,880,725 members
Please Sign up or sign in to vote.
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
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

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

species0: [ 0.. Maxspecies0 ]
species1: [ 0.. Maxspecies1 ]
...
speciesN-1: [ 0.. MaxspeciesN−1 ]

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

(Maxspecies0+1) * (Maxspecies1+1) *... (MaxspeciesN−1+1).

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

—SA
 
Share this answer
 
v3
Comments
BillWoodruff 20-Oct-15 3:32am    
+5 a great example of answering a student/newcomer question/scenario with a response that educates, but does not do their work for them.

see my comment above on why I think this becomes a more complex problem than the usual combinatorial scenario.
Maciej Los 20-Oct-15 12:03pm    
5ed!
Sergey Alexandrovich Kryukov 20-Oct-15 17:52pm    
Thank you, Maciej.
—SA
Patrice T 20-Oct-15 14:47pm    
I am not sure it is as complicated as the knapsack problem.
3 nested loops look enough for me, rather easy.

looks like brute force is still the best to enumerate all responses.
Sergey Alexandrovich Kryukov 20-Oct-15 17:51pm    
No, it is not that complicated, in full sense of it, but this is the right place to look at.
In particular, if you read about Knapsack, you will find a theoretical confirmation of your guess about the brute force; that's why it's dubbed NP-Complete. :-)
—SA

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900