# Help with Knapsack Problem

Hey guys,

I’m a pretty average self-taught programmer, but in no way do I have a background in math or programming. Therefore, having come across the need to solve this problem is pretty hard on me. I’ve been researching the problem for awhile now and trying to figure out how I can adapt code I’ve seen about it to my specific need, but I’m really stomped.

If anyone is willing to help me come up with some code, I would be highly appreciative.

The situation,

In my game I have AI that each have randomly generated “Ratings”. Then I also have a database of cards that are used in the game (it’s somewhat a card game) and each card has a rating as well.

What I need to do is generated a deck for AI that is as close as possible to their rating, but also be no less than 10 cards or no higher than 20. Also it needs to have some random elements to it, because if you fight two AI with the same rating, they still shouldn’t have the same deck.

Now most knapsack problem solutions I’ve seen would throw all the possible options (for me ratings) and output the ones that would equal the sum rating. I actually need it to return the ID of the card, because some cards have the same rating.

For added information, I have a static List of each card in the game that can be accessed, which are stored as their own Card class holding the variables of “Card ID, Rating, etc…”.

Thoughts?

The knapsack algorithm from Wikipedia is this pseudo-code:

``````// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)

for j from 0 to W do:
m[0, j] := 0

for i from 1 to n do:
for j from 0 to W do:
if w[i] > j then:
m[i, j] := m[i-1, j]
else:
m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
``````

What you’ll want to do is that instead of just having the m[i, w] contain the maximum value found for that weight and number of items, it should also contain a collection of all of the items included.

The way to keep and update that collection is probably through a hashset over ID’s, as it’s fast to add and remove things from that.

Hm yea… @Baste , as I said I don’t have a math or programming background. So I kinda have no idea what all that is or how to read it and have any comprehension of it.

In fact I’ve never even seen the word “from” in programming before…

``````    public static List<Card> Generate(List<Card> cardDatabase, int minCards, int maxCards, int targetRating)
{
List<Card> deck = new List<Card>();

//math

return deck;
}
``````

I was thinking I’d just pass in my List (since it has the card type which I can easily read both my cardID and ratings from).

That’s not a specific programming language. It’s just pseudocode - so they’re writing out what needs to happen without any of the nasty details of a language to deal with.

“from 1 to n” means exactly what it says. The syntax is a bit strange, I’d have written it as:

``````for i in from 1 to n do:
``````

In C# terms, that would be:

``````for(int i = 1; i <= n; i++) {
``````

I’d start googling for C# knapsack to see examples of C# implementations, and go from there.

1 Like

@Baste (and anyone else), so this is how far I’ve gotten?

``````public static List<Card> Generate(List<Card> cardDatabase, int minCards, int maxCards, int targetRating, out int totalValue)
{
List<Card> cardDB = Fisher_Yates_CardDeck_Shuffle (cardDatabase);

int cards = Random.Range (minCards, maxCards + 1);
int[,] ratings = new int[cardDB.Count + 1, targetRating + 1];
bool[,] keep = new bool [cardDB.Count + 1, targetRating + 1];

for (int i = 1; i < cardDB.Count; i++) {

Card currentCard = cardDB[i - 1];
for (int space = 1; space <= targetRating; space++) {

if (space >= currentCard.rating) {

int remainingSpace = space - currentCard.rating;
int remainingSpaceValue = 0;

if (remainingSpace > 0) {
remainingSpaceValue = ratings[i - 1, remainingSpace];
}

int currentItemTotalValue = currentCard.rating + remainingSpaceValue;
if (currentItemTotalValue > ratings[i - 1, space]) {
keep[i, space] = true;
ratings[i, space] = currentItemTotalValue;

}else{
keep[i, space] = false;
ratings[i, space] = ratings[i - 1, space];
}
}
}
}

List<Card> deck = new List<Card>();

int remainSpace = targetRating;
int card = cardDB.Count;

while (card > 0) {

bool toBePacked = keep[card, remainSpace];
if (toBePacked) {
remainSpace = remainSpace - cardDB[card - 1].rating;
}
card--;
}

totalValue = ratings[cardDB.Count, targetRating];
Debug.Log ("DeckGen Sum Rating: " + totalValue);
return deck;
}

private static List<Card> Fisher_Yates_CardDeck_Shuffle (List<Card>cardDatabase) {

System.Random _random = new System.Random ();

Card myGO;

int n = cardDatabase.Count;
for (int i = 0; i < n; i++)
{
int r = i + (int)(_random.NextDouble() * (n - i));
myGO = cardDatabase[r];
cardDatabase[r] = cardDatabase[i];
cardDatabase[i] = myGO;
}

return cardDatabase;
}
``````

I haven’t found a way to make sure that the amount of cards in cardDB is within my minimum and maximum cards limits.

As well it currently picks 1 really high rating card in the database and then goes down the list in order finding suitable ratings. (Which leads to them picking very similar cards due to very similar cardIDs.) I trie dto fix this with the Fisher Yates Shuffle but it didn’t seem to change the result.