-1
$\begingroup$

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];
}
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 29 '18 at 15:36
  • $\begingroup$ 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 $\endgroup$ – TomP Mar 29 '18 at 20:25
1
$\begingroup$

You have to add one more dimension (condition) to K. The 3rd dimension is your flag. Don't look at the 3rd dimension as boolean, but as a value. So vegetables have the 3rd dimension as value 1, fruits as 0.
In the 2nd dimension you always add weight. (+5, +8 ..and so on)
In the 3rd dimension you will always add +1, or 0.

It looks like a HW, so I will only hint the answer here:

  • when building the K table, iterate over the 3rd dimension too
  • fill the first values with 0 as in rows and columns
  • there are now 2 conditions. the weight of an item has to be <= as actual weight w, the vegetables "size" has to be <= as actual vegetables count of knapsack
  • In the MAX function you have to look to 3rd dimension exactly the same as you are looking to the 2nd

When you have your final answer, you can look backward in your K table which items you have used. Tushar Roy (at the end of the video) explains it how to do it in 2d knapsack problem, but it is the same as in 3d. https://www.youtube.com/watch?v=8LusJS5-AGo

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.