{"id":"83145c0d-1e1c-47a6-893b-2b4cf9d9fd77","name":"Print All Results In 0-1 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 overflowing it's capacity.\r\n5. Also, you have to print the indices of items that should be selected to make maximum profit.\r\n6. You have to print all such configurations.\r\n\r\nNote -> Each item can be taken 0 or 1 number of times. You are not allowed to put the same item again and again.","inputFormat":"A number n\r\nA number m\r\ne11\r\ne12..\r\ne21\r\ne22..\r\n.. n * m number of elements","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= n &lt;= 10^2\r\n1 &lt;= m &lt;= 10^2\r\n0 &lt;= e1, e2, .. n * m elements &lt;= 1000","sampleCode":{"cpp":{"code":""},"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 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n\r\n int[] values = new int[n];\r\n String str1 = br.readLine();\r\n for (int i = 0; i < n; i++) {\r\n values[i] = Integer.parseInt(str1.split(\" \")[i]);\r\n }\r\n\r\n int[] wts = new int[n];\r\n String str2 = br.readLine();\r\n for (int i = 0; i < n; i++) {\r\n wts[i] = Integer.parseInt(str2.split(\" \")[i]);\r\n }\r\n\r\n int cap = Integer.parseInt(br.readLine());\r\n\r\n //write your code here\r\n \r\n }\r\n}\r\n\r\n\r\n \r\n\r\n\r\n \r\n\r\n\r\n "},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n15 14 10 45 30\r\n2 5 1 3 4\r\n7","sampleOutput":"75\r\n3 4 \r\n","questionVideo":"https://www.youtube.com/embed/YH6M9WFp02g?end=84","hints":[],"associated":[],"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":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"4cf9071c-1859-4495-bc96-fc4ded0918be","name":"Print All Results In 0-1 Knapsack","slug":"print-all-results-in-0-1-knapsack","type":1}],"next":{"id":"92452ecc-ca5f-4039-8c9c-a631ad2e900e","name":"print all results in 0-1 knapsack MCQ","type":0,"slug":"print-all-results-in-0-1-knapsack-mcq"},"prev":{"id":"1a1d6d5c-8b87-4d19-ad96-eed5b429627f","name":"PRINT ALL LONGEST INCREASING SUBSEQUENCES","type":3,"slug":"print-all-longest-increasing-subsequences"}}}

Print All Results In 0-1 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. 5. Also, you have to print the indices of items that should be selected to make maximum profit. 6. You have to print all such configurations. 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":"83145c0d-1e1c-47a6-893b-2b4cf9d9fd77","name":"Print All Results In 0-1 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 overflowing it's capacity.\r\n5. Also, you have to print the indices of items that should be selected to make maximum profit.\r\n6. You have to print all such configurations.\r\n\r\nNote -> Each item can be taken 0 or 1 number of times. You are not allowed to put the same item again and again.","inputFormat":"A number n\r\nA number m\r\ne11\r\ne12..\r\ne21\r\ne22..\r\n.. n * m number of elements","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= n &lt;= 10^2\r\n1 &lt;= m &lt;= 10^2\r\n0 &lt;= e1, e2, .. n * m elements &lt;= 1000","sampleCode":{"cpp":{"code":""},"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 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n\r\n int[] values = new int[n];\r\n String str1 = br.readLine();\r\n for (int i = 0; i < n; i++) {\r\n values[i] = Integer.parseInt(str1.split(\" \")[i]);\r\n }\r\n\r\n int[] wts = new int[n];\r\n String str2 = br.readLine();\r\n for (int i = 0; i < n; i++) {\r\n wts[i] = Integer.parseInt(str2.split(\" \")[i]);\r\n }\r\n\r\n int cap = Integer.parseInt(br.readLine());\r\n\r\n //write your code here\r\n \r\n }\r\n}\r\n\r\n\r\n \r\n\r\n\r\n \r\n\r\n\r\n "},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n15 14 10 45 30\r\n2 5 1 3 4\r\n7","sampleOutput":"75\r\n3 4 \r\n","questionVideo":"https://www.youtube.com/embed/YH6M9WFp02g?end=84","hints":[],"associated":[],"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":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"4cf9071c-1859-4495-bc96-fc4ded0918be","name":"Print All Results In 0-1 Knapsack","slug":"print-all-results-in-0-1-knapsack","type":1}],"next":{"id":"92452ecc-ca5f-4039-8c9c-a631ad2e900e","name":"print all results in 0-1 knapsack MCQ","type":0,"slug":"print-all-results-in-0-1-knapsack-mcq"},"prev":{"id":"1a1d6d5c-8b87-4d19-ad96-eed5b429627f","name":"PRINT ALL LONGEST INCREASING SUBSEQUENCES","type":3,"slug":"print-all-longest-increasing-subsequences"}}}
plane

Editor

Loading...

Print All Results In 0-1 Knapsack

medium

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. 5. Also, you have to print the indices of items that should be selected to make maximum profit. 6. You have to print all such configurations. 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 <= 10^2 1 <= m <= 10^2 0 <= e1, e2, .. n * m elements <= 1000

Format

Input

A number n A number m e11 e12.. e21 e22.. .. n * m number of elements

Output

Check the sample output and question video.

Example

Sample Input

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

Sample Output

75 3 4

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode