0

This may be a simple question for those know-how guys. But I cannot figure it out by myself.

Suppose there are a large number of objects that I need to select some from. Each object has two known variables: cost and benefit. I have a budget, say $1000. How could I find out which objects I should buy to maximize the total benefit within the given budget? I want a numeric optimization solution. Thanks!

Improve this question
2
  • Is the benefit monetary? Or do you simply express benefits in some arbitrary unit of "benefit". If it is just "benefit", @Carl is spot on the money. If the benefit is monetary, then you're looking at a different situation, because the benefit means you would alter your balance, and therefore the cost you can afford to buy. Commented Mar 29, 2011 at 23:45
  • I did not think that far. That will make the problem much more complicated. Commented Mar 30, 2011 at 1:33

3 Answers 3

Reset to default
3

Your problem is called the "knapsack problem". You can read more on the wikipedia page. Translating the nomenclature from your original question into that of the wikipedia article, your problem's "cost" is the knapsack problem's "weight". Your problem's "benefit" is the knapsack problem's "value".

Finding an exact solution is an NP-complete problem, so be prepared for slow results if you have a lot of objects to choose from!

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks! The knapsack problem is exactly my original question. But my "real problem" is a little complicated than this standard problem. I read about a solution of the knapsack problem (dynamic programming solution?) and felt it may not solve my "real problem". I describe my real problem as following. Wish you could give me some suggestions on how to solve it.
Suppose "value" of each item is not constant. The total "value" of the selected items is a function of two variables (x, y) of the selected items: Sum(x_i)/Sum(y_i). Given the restrict on total weight, how to choose items to get highest value? Any suggestion on this problem?
0

You might also look into Linear Programming. From MathWorld:

Simplistically, linear programming is the optimization of an outcome based on some set of constraints using a linear mathematical model.

Improve this answer

Comments

0

Yes, as stated before, this is the knapsack problem and I would choose to use linear programming.

The key to this problem is storing data so that you do not need to recompute things more than once (if enough memory is available). There are two general ways to go about linear programming: top-down, and bottom - up. This one is a bottom up problem.

(in general) Find base case values, what is the most optimal object to select for a small case. Then build on this. If we allow ourselves to spend more money what is the best combination of objects for that small increment in money. Possibilities could be taking more of what you previously had, taking one new object and replacing the old one, taking another small object that will still keep you under your budget etc.

Like I said, the main idea is to not recompute values. If you follow this pattern, you will get to a high number and find that in order to buy X amount of dollars worth of goods, the best solution is combining what you had for two smaller cases.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.