Skip to main content

Zero One Knapsack | Recursion

 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.

Input Format

A number n

v1 v2 .. n number of elements

w1 w2 .. n number of elements

A number cap

Output Format

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

Constraints

1 <= n <= 20

0 <= v1, v2, .. n elements <= 50

0 < w1, w2, .. n elements <= 10

0 < cap <= 10

Sample Input

5

15 14 10 45 30

2 5 1 3 4

7

Sample Output

75


Solution:

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int wt[] = new int[n], val[] = new int[n];
        for(int i=0;i<n;i++)
            val[i] = sc.nextInt();
        for(int i=0;i<n;i++)
            wt[i] = sc.nextInt();
        int cap = sc.nextInt();
        
        System.out.println(knapsack(0,n,val,wt,cap));
    }
    
    public static int knapsack(int i,int n,int val[],int wt[],int cap){
        if(i>=n || cap<=0) 
            return 0;
        int taken = 0;
        if(cap-wt[i]>=0)
            taken = knapsack(i+1,n,val,wt,cap-wt[i]) + val[i];
        int notTaken = knapsack(i+1,n,val,wt,cap);
        
        return Math.max(taken, notTaken);
    }
}

Comments

Must Read:

Software Engineering Concepts Software Maintenance Test Your Understanding

  Software Engineering Concepts       Software Maintenance            Test Your Understanding

Logic Development Logic Development Test Your Understanding

Logic Development       Logic Development            Test Your Understanding

Programming using Java Hands On - Control Structures | Bill Generation

Bill Generation Tom went to a movie with his friends in a multiplex theatre and during break time he bought pizzas, puffs and cool drinks.  Consider   the following prices :  Rs.100/pizza Rs.20/puffs Rs.10/cooldrink Generate a bill for What Tom has bought. Sample Input 1: Enter the no of pizzas bought:10 Enter the no of puffs bought:12 Enter the no of cool drinks bought:5 Sample Output 1: Bill Details No of pizzas:10 No of puffs:12 No of cooldrinks:5 Total price=1290 ENJOY THE SHOW!!! Result Description Summary of tests *Note: All the test cases might not have same weightage +------------------------------+ | 6 tests run/ 6 tests passed | +------------------------------+

Zig Zag Pattern

  /* @ToDo     Zig Zag Pattern         *               *                *       *       *       *        *               *               *        */ #include   <iostream> using   namespace   std ; int   main (){       #ifndef  ONLINE_JUDGE          freopen ( "../asset/input.txt" , "r" , stdin );          freopen (...

RDBMS Data Definition Language | Drop Mobile Specification table (parent)

  RDBMS  Data Definition Language  Drop Mobile Specification table (parent) Refer the following schema and drop Mobile Specification table. (Hint: To drop parent table all associate tables need to be dropped or Use 'cascade constraints' command) Evaluation Result: Result Description Summary of tests +------------------------------+ | 1 tests run / 1 test passed | +------------------------------+

RDBMS Data Definition Language | Create Distributor table

  Write a query to create Distributor table with constraints mentioned.  Refer the below schema  Result Description Summary of tests +------------------------------+ | 3 tests run / 3 test passed | +------------------------------+

Star Pattern

  /* @ToDo     Star Pattern                  *                *   *   *            *   *   *   *   *        *   *   *   *   *   *   *    *   *   *   *   *   *   *   *   *    *   *   *   *   *   *   *   *   *        *  ...

Data Formats ( XML & JSON ) XML AND JSON XML AND JSON | Quiz 2 & 3

Data Formats ( XML & JSON )  XML AND JSON  XML AND JSON Quiz 2 & 3  

Subscribe to Get's Answer by Email