Greedy algorithm implementation

Page 1 of 1

4 Replies - 36259 Views - Last Post: 19 September 2009 - 11:10 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=126334&amp;s=36e090725594df911a2c769c83290913&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 sonictrio

Reputation: 0
• Posts: 26
• Joined: 09-September 09

Greedy algorithm implementation

Posted 16 September 2009 - 09:24 PM

Hi there,

I'm working on a greedy algorithm that will take 3 inputs (m, n, t). m and n are the time it takes to finish one task (both tasks are equal in value) and t is the time given to finish those tasks. I have to maximize the amount of tasks finished (can be as many m or n as I can take, or a combination of both) while making sure that t is kept to a minimum. I then have to print out the amount of tasks completed and the time not spent.

I thought about this for a while and came up with the idea that if the minimum of (m, n) divides evenly into t then that maximizes the tasks finished and minimizes time not spent doing the tasks. For example,

if 3 2 10 is input then 5 0 will be the output.

The code I have done so far looks like this: (where store[] is the array that is storing the numbers]

```for(int j = 0; j < store.length; j += 3){
m = store[j];
n = store[j+1];
t = store[j+2];

if(m > n){
if(t % n == 0){
sum = t / n; //see how many times n goes into t
count = t % n;
System.out.println(sum + " " + count);
}
}
if(n > m){
if(t % m == 0){
sum = t / m;
count = t % m;
System.out.println(sum + " " + count);
}
}
}

```

My problem is this: what do I do when there isn't a simple answer, like the above code checks for. How do I handle if the input is, say, 5 41 112. 8 0 is the output I want (2 x 41 and 6 x 5), how do I go about getting this done?

Is This A Good Question/Topic? 0

Reputation:

Re: Greedy algorithm implementation

Posted 16 September 2009 - 10:08 PM

You are given a list of times for different tasks. First make sure that all the numbers are coprime http://en.wikipedia.org/wiki/Coprime Whenever you find two numbers that are not coprime, keep the smaler one and delete the other one. Think about it, if you have numbers like 3 and 9, you'd never use 9, because you could achieve the same thing with three 3's, giving a better result. To make it easier sort the list in ascending order.

Now, say we have n items in the list - t1, t2, ..., tn and the total time T. The maximum number of jobs would be T/t1 and the minimum number would be T/tn. Now, how do we minimize the remaining T? Let's try to go through all the possible time choices from the one that yields the most times to the one that yields the least times, while keeping track of the remainder. As soon as we reach the remainder of 0 we found our answer. Otherwise we'll go through all the choices, keeping track of the smallest remainder. By the way, the biggest remainder that is possible to yield the correct result is (t1 - 1).

So start with as many t1's as you can. Then subtract t1's and fill the remaining gap with other times, choosing the smallest ones. This would be a greedy algorithm.

This post has been edited by Neumann: 16 September 2009 - 10:18 PM

#3 sonictrio

Reputation: 0
• Posts: 26
• Joined: 09-September 09

Re: Greedy algorithm implementation

Posted 17 September 2009 - 10:47 PM

Neumann, on 16 Sep, 2009 - 09:08 PM, said:

You are given a list of times for different tasks. First make sure that all the numbers are coprime http://en.wikipedia.org/wiki/Coprime Whenever you find two numbers that are not coprime, keep the smaler one and delete the other one. Think about it, if you have numbers like 3 and 9, you'd never use 9, because you could achieve the same thing with three 3's, giving a better result. To make it easier sort the list in ascending order.

Now, say we have n items in the list - t1, t2, ..., tn and the total time T. The maximum number of jobs would be T/t1 and the minimum number would be T/tn. Now, how do we minimize the remaining T? Let's try to go through all the possible time choices from the one that yields the most times to the one that yields the least times, while keeping track of the remainder. As soon as we reach the remainder of 0 we found our answer. Otherwise we'll go through all the choices, keeping track of the smallest remainder. By the way, the biggest remainder that is possible to yield the correct result is (t1 - 1).

So start with as many t1's as you can. Then subtract t1's and fill the remaining gap with other times, choosing the smallest ones. This would be a greedy algorithm.

Hi, thanks for that. I have developed a bit of code (haven't yet included the coprime check but I will). It seems to give me the correct remainder (the lowest possible remainder for m and n) but I can't seem to figure out how to return the amount of tasks completed. This is my code (just dealing with the case n > m for simplicity's sake)

```						if(n > m){
if(t % m == 0){
sum = t / m;
count = t % m;
System.out.println(sum + " " + count);  //it's simple for this case as t/m is even
}
else{
while(sum <= time){
sum = sum + m;
temp = time % sum;
remainder = time % m;
if(temp < remainder){
remainder = temp;
}
}
while(sum > 0){
sum = sum - m;
sum = sum + n;
temp = time % sum;
if(temp < remainder){
remainder = temp;
}
sum = sum - n;
}
System.out.println([***need to track tasks completed***] + " " + remainder);
}

}

```

Any more help is enormously appreciated.

[edit: seeing as I will only ever have 2 tasks (m,n) in my list I just did a simple comparison rather than sort them in ascending order]

This post has been edited by sonictrio: 17 September 2009 - 10:49 PM

#4 sonictrio

Reputation: 0
• Posts: 26
• Joined: 09-September 09

Re: Greedy algorithm implementation

Posted 18 September 2009 - 02:14 AM

I've tried a few different things and this is what my code looks like now (still wrong)

```if(m > n){
if(t % n == 0){
sum = t / n; //see how many times n goes into t
count = t % n;
System.out.println(sum + " " + count);
}
else{
while(sum <= time){
sum = sum + n;
x = time/n;
temp = time % sum;
remainder = time % n;
if(temp < remainder){
remainder = temp;
}
}
while(sum > 0){
sum = sum - n;
x = x - n;
sum = sum + m;
y = time - n / m;
temp = time % sum;
if(temp < remainder){
remainder = temp;
}
sum = sum - m;
}
if(x>y){
z = y;
}
else{
z = x;
}
System.out.println(z + " " + remainder);
}
}

```

#5 sonictrio

Reputation: 0
• Posts: 26
• Joined: 09-September 09

Re: Greedy algorithm implementation

Posted 19 September 2009 - 11:10 PM

sonictrio, on 18 Sep, 2009 - 01:14 AM, said:

I've tried a few different things and this is what my code looks like now (still wrong)

```if(m > n){
if(t % n == 0){
sum = t / n; //see how many times n goes into t
count = t % n;
System.out.println(sum + " " + count);
}
else{
while(sum <= time){
sum = sum + n;
x = time/n;
temp = time % sum;
remainder = time % n;
if(temp < remainder){
remainder = temp;
}
}
while(sum > 0){
sum = sum - n;
x = x - n;
sum = sum + m;
y = time - n / m;
temp = time % sum;
if(temp < remainder){
remainder = temp;
}
sum = sum - m;
}
if(x>y){
z = y;
}
else{
z = x;
}
System.out.println(z + " " + remainder);
}
}

```

bump