Help with writing algorithm

[Van Dugall]

I writing a economic statistics program..

I need to allocate billions of dollars and I
have been shown projects to consider and ith project estimates
its cost to be dollars and claims to generate jobs.

So I have B billions of dollars
n projects
ci dollars
Ji jobs
I guess I have one objective function and one constraint.

Can someone help me with just write the psuedocode to determine which projects to choose to "maximize" job creation
and an estimate of "how many" jobs will be created.

Do you think I should use a greedy algorithm like Prim's or am I off? I not really knowledgable about these types of algorthims

V. Dugall

[JosAH]

If you get j_i jobs for c_i dollars for project i you can use a greedy algorithm where you select the project i that gives you the most jobs for your dollar, i.e. the ratio j_i/c_i is maximal. Repeat while you still have dollars and projects left.

Your single constraint is:

sum(c_i) <= B

and your cost function is

maximize: sum(j_i)

kind regards,

Jos

[jkmyoung]

http://en.wikipedia.org/wiki/Knapsack_problem

Greedy algorithm is probably the best way to go.

[JosAH]

Greedy algorithm is probably the best way to go.

For sure it is: pick the project that gives you the most jobs for the dollar; any other choice is a worse choice. Repeat until you're out of dollars. There are never any 'uphill' steps to take so a steepest descent greedy algorithm will do the job.

kind regards,

Jos