0/1 Knapsack Problem Questions and Answers

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “0/1 Knapsack Problem”.

1. The Knapsack problem is an example of ____________
a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer
View Answer

Answer: b
Explanation: Knapsack problem is an example of 2D dynamic programming.

2. Which of the following methods can be used to solve the Knapsack problem?
a) Brute force algorithm
b) Recursion
c) Dynamic programming
d) Brute force, Recursion and Dynamic Programming
View Answer

Answer: d
Explanation: Brute force, Recursion and Dynamic Programming can be used to solve the knapsack problem.

3. You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?
a) 160
b) 200
c) 170
d) 90
View Answer

Answer: a
Explanation: The maximum value you can get is 160. This can be achieved by choosing the items 1 and 3 that have a total weight of 60.

4. Which of the following problems is equivalent to the 0-1 Knapsack problem?
a) You are given a bag that can carry a maximum weight of W. You are given N items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value
b) You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a maximum of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximized
c) You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S. You have to find the minimum number of coins required to get the sum S
d) You are given a suitcase that can carry a maximum weight of 15kg. You are given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value
View Answer

Answer: b
Explanation: In this case, questions are used instead of items. Each question has a score which is same as each item having a value. Also, each question takes a time t which is same as each item having a weight w. You have to maximize the score in time T which is same as maximizing the value using a bag of weight W.

5. What is the time complexity of the brute force algorithm used to solve the Knapsack problem?
a) O(n)
b) O(n!)
c) O(2ⁿ)
d) O(n³)
View Answer

Answer: c
Explanation: In the brute force algorithm all the subsets of the items are found and the value of each subset is calculated. The subset of items with the maximum value and a weight less than equal to the maximum allowed weight gives the answer. The time taken to calculate all the subsets is O(2ⁿ).

Note: Join free Sanfoundry classes at Telegram or Youtube

6. The 0-1 Knapsack problem can be solved using Greedy algorithm.
a) True
b) False
View Answer

Answer: b
Explanation: The Knapsack problem cannot be solved using the greedy algorithm.

7. Consider the following dynamic programming implementation of the Knapsack problem:

#include<stdio.h>
int find_max(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int knapsack(int W, int *wt, int *val,int n)
{
     int ans[n + 1][W + 1];
     int itm,w;
     for(itm = 0; itm <= n; itm++)
         ans[itm][0] = 0;
     for(w = 0;w <= W; w++)
        ans[0][w] = 0;
     for(itm = 1; itm <= n; itm++)
     {
          for(w = 1; w <= W; w++)
          {
               if(wt[itm - 1] <= w)
                  ans[itm][w] = ______________;
               else
                  ans[itm][w] = ans[itm - 1][w];
          }
     }
     return ans[n][W];
}
int main()
{
     int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
     int ans = knapsack(W, w, v, 3);
     printf("%d",ans);
     return 0;
}

Which of the following lines completes the above code?
a) find_max(ans[itm – 1][w – wt[itm – 1]] + val[itm – 1], ans[itm – 1][w])
b) find_max(ans[itm – 1][w – wt[itm – 1]], ans[itm – 1][w])
c) ans[itm][w] = ans[itm – 1][w];
d) ans[itm+1][w] = ans[itm – 1][w];
View Answer

Answer: a
Explanation: find_max(ans[itm – 1][w – wt[itm – 1]] + val[itm – 1], ans[itm – 1][w]) completes the above code.

8. What is the time complexity of the following dynamic programming implementation of the Knapsack problem with n items and a maximum weight of W?

#include<stdio.h>
int find_max(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int knapsack(int W, int *wt, int *val,int n)
{
     int ans[n + 1][W + 1];
     int itm,w;
     for(itm = 0; itm <= n; itm++)
         ans[itm][0] = 0;
     for(w = 0;w <= W; w++)
        ans[0][w] = 0;
     for(itm = 1; itm <= n; itm++)
     {
          for(w = 1; w <= W; w++)
          {
               if(wt[itm - 1] <= w)
                 ans[itm][w] = find_max(ans[itm - 1][w-wt[itm - 1]]+val[itm - 1], ans[itm - 1][w]);
               else
                  ans[itm][w] = ans[itm - 1][w];
          }
     }
     return ans[n][W];
}
int main()
{
     int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
     int ans = knapsack(W, w, v, 3);
     printf("%d",ans);
     return 0;
}

a) O(n)
b) O(n + w)
c) O(nW)
d) O(n²)
View Answer

Answer: c
Explanation: The time complexity of the above dynamic programming implementation of the Knapsack problem is O(nW).

9. What is the space complexity of the following dynamic programming implementation of the Knapsack problem?

#include<stdio.h>
int find_max(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int knapsack(int W, int *wt, int *val,int n)
{
     int ans[n + 1][W + 1];
     int itm,w;
     for(itm = 0; itm <= n; itm++)
         ans[itm][0] = 0;
     for(w = 0;w <= W; w++)
        ans[0][w] = 0;
     for(itm = 1; itm <= n; itm++)
     {
          for(w = 1; w <= W; w++)
          {
               if(wt[itm - 1] <= w)
                ans[itm][w] = find_max(ans[itm - 1][w - wt[itm - 1]]+val[itm - 1], ans[itm - 1][w]);
               else
                ans[itm][w] = ans[itm - 1][w];
          }
     }
     return ans[n][W];
}
int main()
{
     int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
     int ans = knapsack(W, w, v, 3);
     printf("%d",ans);
     return 0;
}

a) O(n)
b) O(n + w)
c) O(nW)
d) O(n²)
View Answer

Answer: c
Explanation: The space complexity of the above dynamic programming implementation of the Knapsack problem is O(nW).

10. What is the output of the following code?

#include<stdio.h>
int find_max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int knapsack(int W, int *wt, int *val,int n)
{
     int ans[n + 1][W + 1];
     int itm,w;
     for(itm = 0; itm <= n; itm++)
         ans[itm][0] = 0;
     for(w = 0;w <= W; w++)
         ans[0][w] = 0;
     for(itm = 1; itm <= n; itm++)
     {
          for(w = 1; w <= W; w++)
          {
               if(wt[itm - 1] <= w)
                ans[itm][w] = find_max(ans[itm - 1][w-wt[itm - 1]]+val[itm - 1], ans[itm - 1][w]);
               else
                ans[itm][w] = ans[itm - 1][w];
          }
     }
     return ans[n][W];
}
int main()
{
     int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
     int ans = knapsack(W, w, v, 3);
     printf("%d",ans);
     return 0;
}

a) 120
b) 100
c) 180
d) 220
View Answer

Answer: d
Explanation: The output of the above code is 220.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

« Prev - Data Structure Questions and Answers – Minimum Number of Jumps

» Next - Data Structure Questions and Answers – Matrix-chain Multiplication

Related Posts:

Recommended Articles: