10026 - Shoemaker's Problem

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

jhkim
New poster
Posts: 3
Joined: Fri Jun 27, 2003 7:47 pm

10026 - Shoemaker's Problem

Post by jhkim » Fri Jun 27, 2003 7:50 pm

could someone give me an algorithm for this problem?
can't think of one except a backtracking solution that would take FOREVER. not sure how your supposed to sort the fields.

Thanks.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sat Jun 28, 2003 11:34 am

A greedy algorithm suffices. :)
JongMan @ Yonsei

jhkim
New poster
Posts: 3
Joined: Fri Jun 27, 2003 7:47 pm

Greedy Solution

Post by jhkim » Sat Jun 28, 2003 9:40 pm

I thought about a greedy solution, but it didn't work.
For example with the input,
3 4 // (index 0)
2 2 // (index 1)
5 5 // (index 2)

You would first select 1 because (2 * 4) + (2 * 5) is the optimal solution in that case, but you should actually select index 0 instead.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sun Jun 29, 2003 4:04 am

I think you misunderstood the problem?

In this case my program's output is 1 2 3.
Choosing 2 (index 1) is not appropriate because a penalty for a job is the product of delays took before starting the job and it's fine per day. So if in the case

3 4
2 2
5 5

if you take order 2 3 1,
2 2 - > no penalty
5 5 -> 2 * 5 = 10
3 4 -> (2+5) * 4 = 7 * 4 = 28
total = 38

if you take order 2 1 3,
2 2 - > no penalty
3 4 -> 2 * 4 = 8
5 5 -> 5 * 5 = 25
total = 33

but in the order 1 2 3,
3 4 -> no penalty
2 2 -> 3 * 2
5 5 -> 5 * 5
total = 31

Hope I helped, but I became curios myself about my solution. :-? It's written a long ago and I didn't leave any notes or proofs for the algorithm.. so if you notice any counterexample or proof please reply.

Best regards
JongMan @ Yonsei

jhkim
New poster
Posts: 3
Joined: Fri Jun 27, 2003 7:47 pm

got it

Post by jhkim » Sun Jun 29, 2003 7:37 am

Thanks for the help Chingu,
I solved the problem. Your right, a greedy solution does work,
I was just being greedy in the wrong way :) Your good real good

Jin

PJYelton
New poster
Posts: 20
Joined: Fri May 30, 2003 6:56 pm

10026 Shoemaker - Greedy algorithm?

Post by PJYelton » Fri Aug 01, 2003 8:25 pm

I assume a greedy algorithm will solve this one, but the one I used got a WA. Basically I just kept choosing whichever task would cost the most money if it were left until the end. Is this the way to do it? And if so, then what is wrong with my program? Here it is:
[cpp]
/* @JUDGE_ID: 32250TW 10026 C++ "Simple Iteration" */
/* @BEGIN_OF_SOURCE_CODE */
#include <iostream>
#include <vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

struct shoe
{
int time, cost, name;
};

int main()
{
int cases, num, x, y, z;

cin>>cases;

vector<shoe> vec;
vector<int> retVec;

for (x=0; x<cases; x++)
{
vec.clear();
retVec.clear();
cin.ignore(255,'\n');
string buff;
getline(cin,buff);

int totalTime=0;

cin>>num;

for (y=0; y<num; y++)
{
shoe s;
cin>>s.time>>s.cost;
s.name=y+1;
totalTime+=s.time;
vec.push_back(s);
}

int worst;
int wNum;

for (y=0; y<vec.size();)
{
worst=-1;
for (z=0; z<vec.size(); z++)
{
if (vec[z].cost*(totalTime-vec[z].time)>worst)
{
worst=vec[z].cost*(totalTime-vec[z].time);
wNum=z;
}
}
retVec.push_back(vec[wNum].name);
totalTime-=vec[wNum].time;
vec.erase(vec.begin()+wNum);
}

for (y=0; y<retVec.size(); y++)
{
cout<<retVec[y];
if (y!=retVec.size()-1)
cout<<" ";
}
cout<<endl;

if (x!=cases-1)
cout<<endl;
}


return 0;

}
/* @END_OF_SOURCE_CODE */
[/cpp]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Aug 01, 2003 9:22 pm

No, it's the wrong approach.

PJYelton
New poster
Posts: 20
Joined: Fri May 30, 2003 6:56 pm

Post by PJYelton » Fri Aug 01, 2003 9:36 pm

Okay, then can you give me an idea of what the correct approach is or an example of that breaks my above method?

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon Aug 04, 2003 6:22 am

Larry, I would like to know how greedy solve this problem. I Think this is "Task scheduling problem", am I correct ?

Thanks.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Aug 04, 2003 6:38 am

It is if you only have one processor, I guess... but it reduces to a sorting problem..

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Mon Aug 04, 2003 2:16 pm

Indeed, try sorting with an adequate comparison function (if you don't find it, I'll tell you the one I used).
Hint : use stl or libc sorting functions, you'll gain a lot of time.

Billy
New poster
Posts: 3
Joined: Wed Nov 03, 2004 11:40 am

10026

Post by Billy » Wed Nov 03, 2004 11:56 am

Hello, I need a Solution for this problem in a short period of time, but I don't have long time to solve it. For that reason I need that somebody sends a solution for me as long as possible, preferably in language C.

I will thank for it eternally.

You can send me the solution to the email: empecinao2@hotmail.com

Thank you very much.

Billy.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Mon Jun 13, 2005 2:56 am

I am having real hard time finding out the selection function for solving this problem with greedy approach. Some hint is badly needed. :(
You should never take more than you give in the circle of life.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

try this...

Post by sohel » Mon Jun 13, 2005 11:45 am

It's clear that the consideration of just one parameter will not be enough..

.. both fine and time should be the ingredient in determining the value of any (time, fine).

Sorting the data in terms of time required per unit fine should lead you to the right direction.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Re: try this...

Post by Mohammad Mahmudur Rahman » Mon Jun 13, 2005 3:40 pm

sohel wrote:Sorting the data in terms of time required per unit fine should lead you to the right direction.
If this is the case, then come some real problems. I did exactly this & this resulted in WA. So, I started wondering what the actual strategy might be. :o Well, there may be some floating point error....
You should never take more than you give in the circle of life.

Post Reply

Return to “Volume 100 (10000-10099)”