10026 - Shoemaker's Problem

[jhkim]

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.]

A greedy algorithm suffices.

[jhkim]

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.]

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

[jhkim]

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]

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]

No, it's the wrong approach.

[PJYelton]

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]

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

Thanks.

[Larry]

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

[Julien Cornebise]

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]

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]

I am having real hard time finding out the selection function for solving this problem with greedy approach. Some hint is badly needed.

[sohel]

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]

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. Well, there may be some floating point error....