Is there an algorithm that can get the highest value with cost and size limits?

Question

I have a collection of cards. Each card has a cost and also a value. The higher the value, the better the card.

I want to make a hand of up to 9 cards from the collection. I have to keep the total cost of my hand under 70. How do I make the hand with the highest total value?

The numbers 9 and 70 are arbitrary but work for this sample collection (value,cost)

collection = [
    [390,13],
    [294,7],
    [393,7],
    [448,7],
    [235,9],
    [389,9],
    [306,7],
    [263,8],
    [231,9],
    [256,7],
    [396,9],
    [379,9],
    [306,10],
    [240,9],
    [259,4],
    [160,4],
    [225,4],
    [190,3],
    [141,3],
    [188,3],
    [190,4],
    [192,4],
    [192,3],
    [282,5],
    [192,4],
    [169,3],
    [253,4],
    [219,4],
    [240,5]
]

In knapsack terms

Maximize Sum(V[i]x[i]) i from 1 to n

Subject to Sum(W[i]x[i]) <= 70 i from 1 to n

and Sum(x[i]) <= 9 i from 1 to n

where x[i] is 0 or 1

V is the value of each card

W is the weight of each card

Answer 1

Here is my version of the knapsack problem with the added constraint of number of items (written in python). https://github.com/slek120/AutoDeck

In the normal knapsack problem, you make sets that give the highest value for a total cost starting from zero and incrementing until max cost is reached. The next set is the better of the previous set or the set with total cost - cost of item with the item appended. Since there is an item limit, instead of just appending the item, items have to be replaced. So instead, the set with total cost - cost of item + cost of replaced item is used.

I also created a greedy algorithm that works much faster but doesn't give the best answer. In this case, you fill the knapsack with the most cost efficient items until the item limit is reached. Then replace the item with the next most cost efficient item that gives the most reward. Continue until max cost is reached.

Answer 2

just use dynamic programming.

value(x) = max(value(x-i),value(i))

value(x) means the maxium value you can got in x cost, and you store it in an array let's name it V, and it should be static.

then clearly

    V[0] = 0,

and deep in function value.

value(x){

maxValue = 0;
for(i = 1, i < x,i++){
    maxValue = max( (V[i] + V[x-i]) , maxValue); 
}

    V[x] = max(maxValue,pickMax(x))
}

and in function

   pickMax(x)

you just pick the most valuable element you can get in cost of x.

you run value(1),value(2)....value(x); then you got the answer.