d****n
发帖数: 233 | 1 you are provided a String array like so {"1 5 40", "6 7 20","4 7 40"}
Each row item represents the "JOB" you can do..
first number represents the Start time and Second number represents the end
time.. and third number represents the money you will get if you do this job
..
In the example above, obviously you cannot do all the three jobs, because
jobs 1 and 3 clash..so you can either do Jobs 1 and 2 or you can do job 3..
It is profittable to do Jobs 1 and 2 as that will give you 20+40, 60$.
Your | B*****t
发帖数: 335 | 2 two approaches. first sort the jobs according the starting time.
1) backtracking + branch pruning
2) dp, f[i][j] = max(f[k][j], f[k-1][t.start[i]] + value[i]) 0<=k=t.
end[i]; greedy search the max value in above dp equation would optimize it. | d****n
发帖数: 233 | 3 BlueAnt, can you write more details? Thx. | b********h
发帖数: 119 | 4 A possible DP solution could be formulated as follow:
1. sort the jobs by finishing time
2. define D[i] as the maximum money you can make by considering jobs 1 to i.
define job i and j compatible if their time don't overlap.Then
D[i] = max{D[k]+Money[i], D[i-1]}, where k is the latest job that is
compatible to i | d****n
发帖数: 233 | 5 Thanks bladesmith, your DP solution looks correct to me.
I also worked out a solution without using DP.
I paste it here and hope someone can correct me if I'm wrong, some basic
validations are skipped:
typedef struct Job {
int payAmount;
int startTime; // [0 23]
int endTime // [1, 24] endtime >= startime+1;
}
// This function returns the max amount of payment a worker
// can make from the jobs
int FindMaxTotalPayment(Job *jobs, int N)
{
//
// (Skipped) 1.
// Sort
【在 b********h 的大作中提到】
: A possible DP solution could be formulated as follow:
: 1. sort the jobs by finishing time
: 2. define D[i] as the maximum money you can make by considering jobs 1 to i.
: define job i and j compatible if their time don't overlap.Then
: D[i] = max{D[k]+Money[i], D[i-1]}, where k is the latest job that is
: compatible to i
| b********h
发帖数: 119 | 6 Your implementation doesn't seem right to me. Try the following test case:
"1,2,2"
"1,3,3"
"1,4,4"
The expected result is 4. Your algorithm returns 7, i think. I could be
wrong. | d****n
发帖数: 233 | 7 I verified it's correct:
int _tmain(int argc, _TCHAR* argv[])
{
Job jobs[] = { {2, 1, 2}, {3, 1, 3}, {4, 1, 4} };
int maxPay = FindMaxTotalPayment(jobs, 3);
assert(maxPay == 4);
return 0;
}
【在 b********h 的大作中提到】
: Your implementation doesn't seem right to me. Try the following test case:
: "1,2,2"
: "1,3,3"
: "1,4,4"
: The expected result is 4. Your algorithm returns 7, i think. I could be
: wrong.
| B*****t
发帖数: 335 | 8 代码才是硬道理！ 贴个我的code，可能有bug，欢迎指出。另外，DFS没有优化。
#include
#include
using namespace std;
const int N = 10000, MaxTimeValue = 100000;
class Job {
public:
int st, ed, money;
}nd[N];
int n, maxV = 0x80000000;
bool cmp(const Job &a, const Job &b) {
return a.st
}
void dfs(int ix, int endTime, int tot) {
if(ix==n) {
if(tot>maxV) maxV = tot;
return;
}
if(nd[ix].st>=endTime) dfs(ix+1, max(nd[ix].ed,
endTime), tot+nd[ix].mone
【在 d****n 的大作中提到】
: BlueAnt, can you write more details? Thx.
|
|
