Skip to main content

Fractional 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.

Note1: Items can be added to the bag even partially. But you are not allowed to put same items again and again to the bag.


Input Format

A number n

v1 v2 .. n number of elements

w1 w2 .. n number of elements

A number cap

Output Format

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

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: Items can be added to the bag even partially. But you are not allowed to put same items again and again to the bag.


Input Format

A number n

v1 v2 .. n number of elements

w1 w2 .. n number of elements

A number cap

Output Format

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


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 val[] = new int[n],wt[] = 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(fractionalKnapsack(n,val,wt,cap));
    }
    
    public static double fractionalKnapsack(int n, int val[], int wt[], int cap){
        Item[] items = new Item[n];
        for(int i=0;i<n;i++){
            items[i] = new Item();
            items[i].val = val[i];
            items[i].wt = wt[i];
            items[i].ratio = val[i] / (double) wt[i];
        }
        
        Arrays.sort(items);
        
        int i = items.length-1;
        double cost = 0;
        
        while(i>=0 && cap > 0){
            if(items[i].wt<=cap){
                cost += items[i].val;
            }else{
                cost += cap * (items[i].ratio);
            }
            cap -= items[i].wt;
            --i;
        }
        
        return cost;
    }
    
    public static class Item implements Comparable<Item>{
        int val;
        int wt;
        double ratio;
        public int compareTo(Item o){
            if(this.ratio == o.ratio)
                return 0;
            else if(this.ratio > o.ratio)
                return +1;
            else return -1;
        }
    }
}

Comments

Must Read:

Accenture Mock Quiz | Part 1

Question  1 Incorrect Marked out of 1.00 Remove flag Question text Select the true statement ? Select one: a.  Inheritance forms a is-a part of relationship between classes.   b.  Aggregation is the stronger form of Inheritance. c.  Aggregation forms the is-a type of relationship between classes. d.  Aggregation forms a is-a part of relationship between classes. Composition is the stronger form of Aggregation. Feedback The correct answer is: Aggregation forms a is-a part of relationship between classes. Composition is the stronger form of Aggregation. Question  2 Correct Marked out of 1.00 Flag question Question text What is the diagram that depicts the interaction between objects by arranging the objects in time sequence ? Select one: a.  Use Case Diagram b.  Sequence Diagram   c.  Component Diagram d.  Activity Diagram Feedback The correct answer is: Sequence Diagram Question  3 Incorrect Marked out of 1.00 Flag question...

Coin Change Combination

1. You are given a number n, representing the count of coins. 2. You are given n numbers, representing the denominations of n coins. 3. You are given a number "amt". 4. You are required to calculate and print the number of combinations of the n coins using which the       amount "amt" can be paid. Note 1: You have an infinite supply of each coin denomination i.e. same coin denomination can be                    used for many installments in payment of "amt" Note 2: You are required to find the count of combinations and not permutations i.e.                   2 + 2 + 3 = 7 and 2 + 3 + 2 = 7 and 3 + 2 + 2 = 7 are different permutations of same                    combination. You should treat them as 1 and not 3. Input Format A number n n1 n2 .. n number of elements A number amt Output Format A number representing the count of ...

Programming using Java Hands On - Control Structures | Check for Leap Year

  Given a year, check if the year is leap year or not.  If yes, the output should be “Leap Year”.  Else output should be “Not a Leap Year”.  The input should be a positive four digit number.  Else,  the output should be “Invalid Year”. Sample Input  1 : Enter the Year 2016 Sample Output  1 : Leap Year Sample Input  2 : Enter the Year 2001 Sample Output  2 : Not a Leap Year Result Description Summary of tests *Note: All the test cases might not have same weightage +------------------------------+ | 12 tests run/12 tests passed | +------------------------------+

Climb Stairs With Minimum Moves

1. You are given a number n, representing the number of stairs in a staircase. 2. You are on the 0th step and are required to climb to the top. 3. You are given n numbers, where ith element's value represents - till how far from the step you       could jump to in a single move.  You can of-course fewer number of steps in the move. 4. You are required to print the number of minimum moves in which you can reach the top of       staircase. Note -> If there is no path through the staircase print null. Input Format A number n .. n more elements Output Format A number representing the number of ways to climb the stairs from 0 to top. Constraints 0 <= n <= 20 0 <= n1, n2, .. <= 20 Sample Input 10 3 3 0 2 1 2 4 2 0 0 Sample Output 4 Solution: import java.io.*; import java.util.*; public class Main {     public static void main(String[] args) throws Exception {         // write your code here    ...

Subscribe to Get's Answer by Email