10026  Shoemaker's Problem
Moderator: Board moderators
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.
can't think of one except a backtracking solution that would take FOREVER. not sure how your supposed to sort the fields.
Thanks.
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.
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.

 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
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
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*(totalTimevec[z].time)>worst)
{
worst=vec[z].cost*(totalTimevec[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!=cases1)
cout<<endl;
}
return 0;
}
/* @END_OF_SOURCE_CODE */
[/cpp]
[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*(totalTimevec[z].time)>worst)
{
worst=vec[z].cost*(totalTimevec[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!=cases1)
cout<<endl;
}
return 0;
}
/* @END_OF_SOURCE_CODE */
[/cpp]

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

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
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.
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
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.
.. 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.

 Experienced poster
 Posts: 154
 Joined: Sat Apr 17, 2004 9:34 am
 Location: EEE, BUET
Re: try this...
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....sohel wrote:Sorting the data in terms of time required per unit fine should lead you to the right direction.
You should never take more than you give in the circle of life.