# Knapsack progblem with two conditions

I want to create an algorighm (with dynamic programing) similar to 1/0 knapsack problem but, I have one extra condition isVegetable or isFruit.

Assume we have N food items where we know number, weight, value, 0 || 1 where 0 means isFruit and 1 meas isVegetable. We have two conditions, one is max knapsack weight and second is max number of vegetable items

Two condition means ... we cant exceed max knapsack capacity (weight) and there cant bee more than T number of vegetables in knapsack, so yes max value can bee lower than in basic 1/0 knapsack:

    4 // number of fruit items
6 // max knapsack weight
2 // max number of vegetable
// item_number, item_value, item_weight, isFruit || isVegetable
1 8 4 0
2 5 8 1
3 6 1 1
3 6 1 0


Here is an code example for basic 1/0 knapsack. I need to adjust this solution for isVegetable limitation. Any ideas?

int knapSack(int W, int wt[], int val[], int n){
int i, w;
int K[][] = new int[n+1][W+1];

// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}

return K[n][W];
}

• What did you try? Where did you get stuck? We have guidance on how to approach dynamic programming problems; I suggest you follow the systematic approach there, and if you get stuck somewhere, edit the question to show us what progress you've made and what specific step you have a question about. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Mar 29 '18 at 15:36
• Actually I though of using 3 rd dimension (3d array) but It is kinda hard to imagine :/ I was hoping ... that there is some kind of known solution for this version of knapsack – tprieboj Mar 29 '18 at 20:25