# C++ sorting and a little help from u guys

This topic is 4952 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

hi there im currently trying to build a little program that generates the best possible combination of some list say we have a container that has 100% capacity and we fill it with certain items that take up the capacity so item 1 takes 50% of the capacity and is worth 60,000 item 2 takes 20% of the capacity and is worth 30,000 item 3 takes 80% of the capacity and is worth 90,000 item 4 takes 40% of the capacity and is worth 60,000 the program will work out that having items 2 and 3 provides the bewst solution Can someone help me realise this as im having a difficult time thinking of how to do it. thanks [Edited by - rholding2001 on April 24, 2005 7:37:08 AM]

##### Share on other sites
Well this is similar to the bin-packing problem which is NP-Complete, so this may also be NP-Complete in which case the only way to get an optimal solution will be to work out all possible combinations of items and see which is the best.

You could try ordering the list in terms of value from highest to lowest and then ordering things with the same value from smallest capacity to highest capacity and then iterating through the resulting list putting in items until you run out of space. e.g. with your example after order from high value to low value you would have something like:

3
1
4
2

then after ordering values with the same value from low capacity to high capacity:

3
4
1
2

then you'd fit in 3 and 2 giving you an optimal solution (though I don't think you're gonna get an optimal solution in all cases).

##### Share on other sites
If all space the items take up are integer then you could keep an array that has the best option for each capacity (pseudocode):
struct Combination {    int totalValue = 0;    std::vector<int> items;}// the best combination that fills a specific capacityCombination bestCombination[100];for each i in item {    for each cost in [0...100-i.cost) {        int newValue = bestCombination[cost].totalValue + i.value;        if (newValue > bestCombination[cost+i.cost].totalValue) {            // found a better combination for value cost+i.cost            bestCombination[cost+i.cost] = bestCombination[cost];            bestCombination[cost+i.cost].value = newValue;            bestCombination[cost+i.cost].items.push_back(i);        }    }}// the best combination is bestCombination[100]

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633302
• Total Posts
3011276
• ### Who's Online (See full list)

There are no registered users currently online

×