Pseudo code Algorithm for Knapsack Problem with Two Constrains

Question

I'm trying to solve following knapsack problem with two constrains.

What we know:

• List item Total number of items
• List item Weight
• List item Value
• List item If item is fragile or not (true/false)

Constrains:

• List item Maximal weight of knapsack
• List item Maximum number of fragile items knapsack can contain.

Can anyone give me some advice about algorithm i should use, pseudo code or good article?

UPDATE:

Important thing I forgot to mention is that I also need to know which items I putted in the bag.

Answer 1

It looks like a modification to knapsack would solve it.

Let's say we have N items, maximum knapscak weight is W, and max amount of fragile items is F

let's define our dp table as 3-dimensional array dp[N+1][W+1][F+1]

Now dp[n][w][f] stores maximum value we can get if we fill knapsack with some subset of items from first n items, having weight of exacly w and having exacly f fragile items.

frop dp[n][w][f] we can move to states:

• dp[n+1][w][f] if we skip n+1 th item
• dp[n+1][w + weight(n+1)][f + isFragile(n+1)] if we take n+1 th item

so pseudocde:

dp[N+1][W+1][F+1] // memo table, initially filled with -1

 int solve(n,w,f)
{
    if(n > N)return 0;
    if(dp[n][w][f] != -1) return dp[n][w][f];

    dp[n][w][f] = solve(n+1,w,f); //skip item
    if(w + weight(n) <= W && f + isFragile(n) <=F)
    dp[n][w][f] = max(dp[n][w][f], value(n) + solve(n+1, w + weight(n), f + isFragile(n)));

    return dp[n][w][f]
}

print(solve(1,0,0))

Getting the actual subset is also not difficult:

vector<int> getSolution(n,w,f)
{   
    int optimalValue = solve(n,w,f);
    vector<int>answer; //just some dynamic array / arrayList

    while(n <= N)
    {
        if(solve(n+1,w,f) == optimalValue)n++; //if after skipping item we can still get optimal answer we just skip it
        else //otherwise we cant so current item must be taken
        {
            int new_w = w + weight(n);
            int new_f = f + isFragile(n);
            answer.push_back(n); //so we just save its index, and update all values
            optimalValue -= value(n);
            n++;
            w = new_w;
            f = new_f;
        }
    }
    return answer;
}