find the maximum total price for the list of items

[aravinda reddy]

I have to find the maximum total price for the list of items so that
weight should not exceed 14285 and volume should not exceed 17..
I need the best algorithm to find this.. The structure look like this

wmax= 14285
vmax= 17

item weight volume price
==============================
1 1190 1.3 240
2 1374 0.8 229
3 1031 1.7 425
4 1265 1.5 341
5 1218 1.8 177
6 1524 1.9 205
7 1842 0.8 100
8 367 1.3 486
9 1541 1.7 368
10 878 1 351
11 1058 1.1 260
12 2026 1 100
13 1808 1.8 290
14 1803 1.6 253
15 1411 0.7 100

[phoenix911]

plz add some more info...

like should it get the best match to the wmax and vmax? or just iterate down the list and work from the top down, adding until it reaches the wmax/vmax

[aravinda reddy]

first i select all the items, in those i should select items so that weight of all the selected items should not exceed 14285 at the same time volume should not exceed 17 along with this the transporter should not get loss.mean to say he should should get maximum price...getting maximum price is the key factor

[phoenix911]

max price, meaning the cheapest deal? lol or spending the most money?

[aravinda reddy]

no i should get all items list but condition is weight and volume should not exceed at the same time i should get max profit with the selected items

[aravinda reddy]

c consider i enter N items...and each item has some weight volume and price...

i may get N items or N-1 items as the output it doesnot matter but sum of weight and volume of selected items should not exceed the
prescribed value.... and the price of the selected items should be high after all
permutations and combinations and transporter should get profit after all...

we should work on 3 constraints here

1.sum of weight of selected items should not exceed 14285
2.sum of volume of selected items should not exceed 17
3.price should be high after all permutations and combinations

hope u got some idea now

[phoenix911]

read that data into a class, if it isnt already in a class....

then create a seperate list<class> and then just in a while loop list.add(item) ... but in the while loop keep adding the vmax and the wmax... and the price if you want the total of that aswel...

the while condition something like while((vmax < 14286) && (max < 18))

just a rough idea... but im not to sure on the current structure you got going..

hope this gives some idea

[privatevoid]

I think from what you have said you need to get the optimal price for the space/weight allowed a very interesting problem,
this is a version of the multi-dimensional knapsack problem.

See here for an in depth description of the problem.

From the layout of this question I guess that the it stems from an academic assignment and the best answer is dependant on what you are studying but by the looks of it you should consider using an appropriate AI algorithms such as a Genetic Algorithm(GA) or the Ant Algorithm.

[nsq3n]

hi!
i got a formula that i don't quiet understand, coursework, can anyone help

thanks, appreciate lots if you can help
the formula and its descriptions are in a blog please check the link
http://teamntu.blogspot.com/

i also uploaded a image of the formula.
info:
There is a list of n items that are to be send to the location where a certain container is going to (individual lists for each group will be put on the VLP). Each item i is only available once and has an associated weight wi, a volume vi, and a value, which is referred to here as fitness fi. Your task is to write a computer program that can find a list of items that a) fit into the container space available, not exceeding the maximum load wmax or the maximum volume vmax, and b) to maximise the total value ftotal of that shipping:

thanks

[Momerath]

I'd use dynamic programming to generate possible combinations and build upon those, tossing those that violate the constraints. Once done sort the remaining ones by value and take the highest one.