Jump to content
  • Advertisement
Sign in to follow this  
rholding2001

C++ sorting and a little help from u guys

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 capacity
Combination 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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!