开发者

Branch and bound algorithm for maximization of importance

I have a problem that should be solved with branch and bound algorithm, however i'm having a hard time thinking how to solve it. I'cant figure out how to start the branch and bound algorithm.

Here is the problem:

A car has 开发者_如何学Ca maximum weight and volume capacity, and i need to fill the car with packages. Those packages have a determined value of importance, weight and volume. The objective is to put in the car the combination of packages with highest importace value without passing the limits of weight and volume of the car.


For branch and bound you need to know how to describe a partial solution, and how to work out a bound on how good it could possibly be. A partial solution could be a list of packages that you have decided will definitely go in the car, regardless of what else you add. You can work out an upper bound on how much value will go in the car by looking to see how much space and weight is left, and, amongst the packages that are left, what the largest amount of value per unit volume and value per unit weight are.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜