true

Learn Advanced Java coaching from the Best Tutors

• Affordable fees
• 1-1 or Group class
• Flexible Timings
• Verified Tutors

Search in

# Fractional Knapsack

Paras Chawla
29/05/2017 0 0

Algorithm - Fractional Knapsack

import java.util.Scanner;

public class Knapsack01 {

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int n = scan.nextInt(); // 1

int W = scan.nextInt(); // 1000

float value[] = new float[n]; // 500

float weight[] = new float[n]; // 30

float ratio[] = new float[n];

for (int i = 0; i < n; i++) {

value[i] = scan.nextInt();

weight[i] = scan.nextInt();

ratio[i] = value[i] / weight[i];

}

float totalValue = knapSack01(W, value, weight, ratio, n);

System.out.println(totalValue);

}

public static float knapSack01(float W, float[] value, floatweight[], float ratio[],

int n) {

float V = 0;

while (n>0 && W!=0) {

int mI = maxIndex(n, ratio);

float w=min(weight[mI],W);

// W=40,weight[2]=30 // W=10,weight[0]=20;

W = W - w;

V = V + w*ratio[mI];

weight[mI]=weight[mI]-w;

ratio[mI] = 0;

n--;

}

return V;

}

public static float min(float a,float b){

return a>b?b:a;

}

public static int maxIndex(int n, float ratio[]) {

float largest = Integer.MIN_VALUE;

int lastIndex = 0;

for (int i = 0; i < n; i++) {

if (ratio[i] > largest) {

largest = ratio[i];

lastIndex = i;

}

}

return lastIndex;

}

}

Output:

Input: 3 50

60 20 100

50 120 30

Output: 180.0000

0 Dislike

## Other Lessons for You

Films : Advantages and Disadvantages A film is automatically associated with fun, entertainment and relaxation. The next 2 and a half hours are to be enjoyed thoroughly. Work pressures, daily routines,...

MATHS IS EASY
Mathematics is based on formulas and method to use them.The practice make you perfect in this subject. Prepare according to syllabus, try to solve old papers, revise the concept you learned and try to...
M

Mohit S.

Getting A Bit Deeper Into Time Complexity Analysis
What is Time Complexity Analysis? In the last blog, you got a rough idea about the Time Complexity and that was all about to judge how fast the algorithm can run, or putting it in another way, how much...

Current and voltage distribution
a) A current flowing in a wire of a length related to the RF produces an electromagnetic field. This field radiates from the wire and is set free in space. The principles of radiation of electromagnetic...

### Looking for Advanced Java coaching ?

Learn from Best Tutors on UrbanPro.

Are you a Tutor or Training Institute?

Join UrbanPro Today to find students near you

X

### Looking for Advanced Java coaching Classes?

The best tutors for Advanced Java coaching Classes are on UrbanPro

• Select the best Tutor
• Book & Attend a Free Demo
• Pay and start Learning

### Learn Advanced Java coaching with the Best Tutors

The best Tutors for Advanced Java coaching Classes are on UrbanPro