Click here to Skip to main content
15,077,641 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
N fighters are fighting with M monsters. For each fighter, you know the time they need to kill one monster. All the fighters fight simultaneously. The control of each fighter is in your hand. So you can guide each fighter on the number of monsters he has to kill. Now you have to guide the fighters in such a way that the time required to kill all the monsters is minimum possible?

What I have tried:

I am beginner to a programming and I have tried this but I did not get a thought of logic behind this question?
Posted
Updated 3-May-21 14:47pm
v2
Comments
Richard MacCutchan 3-May-21 3:30am
   
Your first problem is to decide which language you want to use and learn that. And if the logic of this problem is too complicated for you, then find some simpler tasks. The tutorials for most languages will help.
Greg Utas 3-May-21 14:25pm
   
I think the problem requires some clarification. "For each fighter" suggests that each fighter can have a different kill time. Also, if one fighter is attacking a monster when another fighter kills his own monster, can the second fighter take over from the first one if he could now kill that monster faster?

This is a kind of Knapsack problem.

You have a bunch of monsters (M) and a bunch of fighters (N). You are asked to figure out the best way (shortest time) to assign fighters to monsters that each monster is (eventually) fought.

Consider the case where you have 2 fighters, with times = {1, 2}, and 1 monster.

If you assign the fighter with time=1, then "all the monsters" are fought in a total time of 1. If you assign the fighter with time=2, then "all the monsters" are fought in a total time of 2.

We assume that faster is better, so the solution with time=1 is better than the solution with time=2.

Now consider what happens if you have two monsters. You could assign F1 to M1 and F2 to M2. Both monsters would be fought in parallel, with a total time of 2 (because F1 would beat M1 in 1 time unit, then wait for F2 to finish).

Alternatively, you could assign F1 to M1, then assign F1 to M2, in sequence. The total time would be 1 + 1 = 2, again. So there are two solutions with the same "best" time.

Now suppose you have 100 monsters, and 2 fighters with time={1, 30}. If you give all the monsters to F1 it will take 100 time. But if you give 3 monsters to F30, then F30 will finish in 30*3 = 90 time, while F1 handles 97 monsters in 97 time, in parallel. This is a better solution, since 97 < 100 time.

This seems like a "dynamic programming" problem. There are a few popular techniques for solving these sorts of problems, all available on Youtube by asking the Duck.
   
Comments
PIEBALDconsult 3-May-21 19:18pm
   
Please just add that to the problem statement. It is not a solution.
merano99 4-May-21 17:36pm
   
I seems a good hint to solve the problem. The questioner asked what logic is behind the problem and the answer seems appropriate.

We are more than willing to help those that are stuck: but that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
   
Lack of detail in question, makes more precise hints impossible. A sample problem may help to understand exact problem.
Example of missing detail is what happen if you put 2 fighter on a single monster?
Do all fighter need same time to kill a monster?
Do all monsters are killed in same time?
Quote:
I am beginner to a programming

Then stop, you are on wrong tracks. What you try to do is like learning to drive a car by winning a Formula 1 GP, it don't work.
Advice: Learn properly programming with tutorials and do as much exercises as possible. As you get experience, you are able to solve problems more and more complicated.
Quote:
Now you have to guide the fighters in such a way that the time required to kill all the monsters is minimum possible?

This is 'Scheduling Optimization', it fall in 'Integer Programming' category which is a very difficult problem for an exact solution.
Integer programming - Wikipedia[^]
The first step to solution is to solve the problem by hand:
- First, find a method to get a solution.
- Second, find how to improve current solution.
- When you can't get a better solution, it is your solution.
This will help you to get a better understanding of how the problem is working. Your method to solve manually the problem is basically your algorithm.
   

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