## 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

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:
A greedy algorithm suffices.
JongMan @ Yonsei

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

### Greedy Solution

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:
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

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?

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:
No, it's the wrong approach.

PJYelton
New poster
Posts: 20
Joined: Fri May 30, 2003 6:56 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
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:
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:
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

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.

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
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.

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

### try this...

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.