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:

RDBMS Data Definition Language | Create Sales_info table

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

Algorithm Analysis and Design Concepts Data Structure and Algorithms Post-Quiz

Algorithm Analysis and Design Concepts       Data Structure and Algorithms            Post-Quiz  

Algorithm Analysis and Design Concepts Analysis of Algorithms Post-Quiz

 Algorithm Analysis and Design Concepts       Analysis of Algorithms            Post-Quiz  

Logic Development | Object Oriented Programming Post Quiz

 Logic Development | Object-Oriented Programming | Post Quiz

Programming using Java Hands On - Control Structures | Print Username

  Print Username Jeffy, who is going to complete the higher education in this year needs to create a simple application which accept the name of a person and welcome them with a message along with their name. She wants to read the data using the class "Scanner". Implement this scenario using Java. Sample Input 1:   Enter the name: Johson Sample Output 1: Welcome Johnson. Sample Input 2:   Enter the name: Stain Polson Sample Output 2: Welcome Stain Polson. Result Description Summary of tests *Note: All the test cases might not have same weightage +------------------------------+ | 2 tests run/ 2 tests passed | +------------------------------+

Logic Development | Object Oriented Programming Pre Quiz

 

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 | +------------------------------+

Data Formats ( XML & JSON ) XML AND JSON | Post-Quiz

  Question   1 Correct Mark 1.00 out of 1.00 Flag question Question text State True or False. JSON is data oriented and does not provide display capabilities. Select one: True   False Feedback The correct answer is 'True'. Question  2 Incorrect Mark 0.00 out of 1.00 Flag question Question text Which one of the following indicators define that either one of the child element must occur within the element? Select one: choice sequence      all any Feedback Your answer is incorrect. The correct answer is: choice Question  3 Correct Mark 1.00 out of 1.00 Flag question Question text JSON object value is accessed by using ________. Select one: dot(.) notation   star(*) notation colon(:) notation dollar($) notation Feedback Your answer is correct. The correct answer is: dot(.) notation Question  4 Correct Mark 1.00 out of 1.00 Flag question Question text Which of the following is a well formed XML document? Select one: <?xml version=”1.0...

RDBMS Data Definition Language | Create Buses table

 efer the below schema and create the buses table. Column Name Datatype Size Constraint Constraint name Bus_no Number 11 Primary key PK_BUSES Bus_name Varchar2 20   Type Varchar2 20   Total_seats Number 11   Avail_seats Number 11     Result Description Summary of tests +------------------------------+ | 3 tests run / 3 test passed | +------------------------------+

Subscribe to Get's Answer by Email