Knapsack with an amount limitation

I'm trying to solve a problem thats some what similar to the knapsack problem but with a twist. At least thats what I have come to think it is anyway. In the knapsack problem we have the weight capacity of the knapsack, the weight and value of the items. My twist to this one is to add a certain amount of slots available to be filled with items. Like this: We have a knapsack with the maximum weight capacity of 30 and it can only hold 6 items regardless of weight. Duplicates are allowed.

I managed to make a recursive function that takes a List containing the same amount of lists that there are slots available

List<List<Item>> workingList
// Example of a list of items.
{"items" : 
    ["name":"item1","value":2,"weight"4],
    ["name":"item2","value":3,"weight"5],
    ["name":"item3","value":4,"weight"6],
    ["name":"item4","value":5,"weight"8]
}

and returning suggested list of items optimal for the weight and value. Problem with this function is that its very greedy. It takes forever (or run out of memory) if I have more than 4 slots and 10 items. I need to be able to fit about 50 items or more and around 3-8 slots. I've looked at some examples of the knapsack problem but can't get a good grip on if it will work for my problem. Is it possible to use the knapsack or is it a completely other approach?

链接地址: http://www.djcxy.com/p/59946.html

上一篇: 背包多重约束

下一篇: 背负数量限制