{"id":"d03ae94e-1af3-4be8-8686-73ece23118bf","name":"Zero One Knapsack","description":"1. You are given a number n, representing the count of items.\r\n2. You are given n numbers, representing the values of n items.\r\n3. You are given n numbers, representing the weights of n items.\r\n3. You are given a number \"cap\", which is the capacity of a bag you've.\r\n4. You are required to calculate and print the maximum value that can be created in the bag without \r\n overflowing it's capacity.\r\n\r\nNote -> Each item can be taken 0 or 1 number of times. You are not allowed to put the same item \r\n again and again.","inputFormat":"A number n\r\nv1 v2 .. n number of elements\r\nw1 w2 .. n number of elements\r\nA number cap","outputFormat":"A number representing the maximum value that can be created in the bag without overflowing it's capacity","constraints":"1 &lt;= n &lt;= 20\r\n0 &lt;= v1, v2, .. n elements &lt;= 50\r\n0 &lt; w1, w2, .. n elements &lt;= 10\r\n0 &lt; cap &lt;= 10","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nvoid zeroOneKnapsack(int n,vector<int> val, vector<int> weight,int cap){\n \n// write your code here\n \n}\n\nint main() {\n \n int n;\n cin >> n;\n \n vector<int> val(n);\n for (int i = 0; i < n; i++) {\n cin >> val[i];\n }\n \n vector<int> weight(n);\n for (int i = 0; i < n; i++) {\n cin >> weight[i];\n }\n \n int cap;\n cin >> cap;\n \n zeroOneKnapsack(n,val,weight,cap);\n\n\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n\r\n }\r\n}"},"python":{"code":"def zeroknapSack(cap, wt, val, n):\n \n # write your code here\n \n \nn = int(input())\n\nst1 = input()\nv=st1.split()\nval=[int(i) for i in v]\n\nst2 = input()\nw = st2.split()\nwt = [int(j) for j in w]\n\ncap = int(input()) \n \nprint(zeroknapSack(cap, wt, val, n))"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n15 14 10 45 30\r\n2 5 1 3 4\r\n7","sampleOutput":"75","questionVideo":"https://www.youtube.com/embed/bUSaenttI24?end=132","hints":[],"associated":[{"id":"164cf271-def4-4930-9d17-6905196f0c27","name":"What is the time complexity of Zero One Knapsack","slug":"what-is-the-time-complexity-of-zero-one-knapsack","type":4},{"id":"4f36f82b-5a5a-4169-bba5-f4419680e3d4","name":"From which direction should we start solving the dp?","slug":"from-which-direction-should-we-start-solving-the-dp","type":4},{"id":"8c433ae6-6458-42d1-b7c4-ea732a789d2d","name":"What will be the size of dp?","slug":"what-will-be-the-size-of-dp","type":4},{"id":"9fdad9f0-dbb2-4777-8ff5-f64ca04ccebb","name":"What is the Space complexity of Zero One Knapsack","slug":"what-is-the-space-complexity-of-zero-one-knapsack","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"52d62581-1313-45fb-aaf0-1d72a45f6a50","name":"Dynamic Programming And Greedy For Beginners","slug":"dynamic-programming-and-greedy-for-beginners","type":0},{"id":"e799431a-a48b-43a3-a41d-10bf35bc0272","name":"Zero One Knapsack","slug":"zero-one-knapsack","type":1}],"next":{"id":"52e053b3-7680-4950-83fe-6d79f5074a38","name":"Zero One Knapsack","type":3,"slug":"zero-one-knapsack"},"prev":{"id":"14689e99-e125-4017-a53b-2f71c54bf5ab","name":"Coin Change - Permutations","type":3,"slug":"coin-change-permutations"}}}

Zero One Knapsack

1. You are given a number n, representing the count of items. 2. You are given n numbers, representing the values of n items. 3. You are given n numbers, representing the weights of n items. 3. You are given a number "cap", which is the capacity of a bag you've. 4. You are required to calculate and print the maximum value that can be created in the bag without overflowing it's capacity. Note -> Each item can be taken 0 or 1 number of times. You are not allowed to put the same item again and again.

{"id":"d03ae94e-1af3-4be8-8686-73ece23118bf","name":"Zero One Knapsack","description":"1. You are given a number n, representing the count of items.\r\n2. You are given n numbers, representing the values of n items.\r\n3. You are given n numbers, representing the weights of n items.\r\n3. You are given a number \"cap\", which is the capacity of a bag you've.\r\n4. You are required to calculate and print the maximum value that can be created in the bag without \r\n overflowing it's capacity.\r\n\r\nNote -> Each item can be taken 0 or 1 number of times. You are not allowed to put the same item \r\n again and again.","inputFormat":"A number n\r\nv1 v2 .. n number of elements\r\nw1 w2 .. n number of elements\r\nA number cap","outputFormat":"A number representing the maximum value that can be created in the bag without overflowing it's capacity","constraints":"1 &lt;= n &lt;= 20\r\n0 &lt;= v1, v2, .. n elements &lt;= 50\r\n0 &lt; w1, w2, .. n elements &lt;= 10\r\n0 &lt; cap &lt;= 10","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nvoid zeroOneKnapsack(int n,vector<int> val, vector<int> weight,int cap){\n \n// write your code here\n \n}\n\nint main() {\n \n int n;\n cin >> n;\n \n vector<int> val(n);\n for (int i = 0; i < n; i++) {\n cin >> val[i];\n }\n \n vector<int> weight(n);\n for (int i = 0; i < n; i++) {\n cin >> weight[i];\n }\n \n int cap;\n cin >> cap;\n \n zeroOneKnapsack(n,val,weight,cap);\n\n\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n\r\n }\r\n}"},"python":{"code":"def zeroknapSack(cap, wt, val, n):\n \n # write your code here\n \n \nn = int(input())\n\nst1 = input()\nv=st1.split()\nval=[int(i) for i in v]\n\nst2 = input()\nw = st2.split()\nwt = [int(j) for j in w]\n\ncap = int(input()) \n \nprint(zeroknapSack(cap, wt, val, n))"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n15 14 10 45 30\r\n2 5 1 3 4\r\n7","sampleOutput":"75","questionVideo":"https://www.youtube.com/embed/bUSaenttI24?end=132","hints":[],"associated":[{"id":"164cf271-def4-4930-9d17-6905196f0c27","name":"What is the time complexity of Zero One Knapsack","slug":"what-is-the-time-complexity-of-zero-one-knapsack","type":4},{"id":"4f36f82b-5a5a-4169-bba5-f4419680e3d4","name":"From which direction should we start solving the dp?","slug":"from-which-direction-should-we-start-solving-the-dp","type":4},{"id":"8c433ae6-6458-42d1-b7c4-ea732a789d2d","name":"What will be the size of dp?","slug":"what-will-be-the-size-of-dp","type":4},{"id":"9fdad9f0-dbb2-4777-8ff5-f64ca04ccebb","name":"What is the Space complexity of Zero One Knapsack","slug":"what-is-the-space-complexity-of-zero-one-knapsack","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"52d62581-1313-45fb-aaf0-1d72a45f6a50","name":"Dynamic Programming And Greedy For Beginners","slug":"dynamic-programming-and-greedy-for-beginners","type":0},{"id":"e799431a-a48b-43a3-a41d-10bf35bc0272","name":"Zero One Knapsack","slug":"zero-one-knapsack","type":1}],"next":{"id":"52e053b3-7680-4950-83fe-6d79f5074a38","name":"Zero One Knapsack","type":3,"slug":"zero-one-knapsack"},"prev":{"id":"14689e99-e125-4017-a53b-2f71c54bf5ab","name":"Coin Change - Permutations","type":3,"slug":"coin-change-permutations"}}}
plane

Editor

Loading...

Zero One Knapsack

easy

1. You are given a number n, representing the count of items. 2. You are given n numbers, representing the values of n items. 3. You are given n numbers, representing the weights of n items. 3. You are given a number "cap", which is the capacity of a bag you've. 4. You are required to calculate and print the maximum value that can be created in the bag without overflowing it's capacity. Note -> Each item can be taken 0 or 1 number of times. You are not allowed to put the same item again and again.

Constraints

1 <= n <= 20 0 <= v1, v2, .. n elements <= 50 0 < w1, w2, .. n elements <= 10 0 < cap <= 10

Format

Input

A number n v1 v2 .. n number of elements w1 w2 .. n number of elements A number cap

Output

A number representing the maximum value that can be created in the bag without overflowing it's capacity

Example

Sample Input

5 15 14 10 45 30 2 5 1 3 4 7

Sample Output

75

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode