Translate into Java // C/C++ program to solve fractional Knapsack Problem #inclu
ID: 3727160 • Letter: T
Question
Translate into Java
// C/C++ program to solve fractional Knapsack Problem
#include <bits/stdc++.h>
using namespace std;
// Stucture for Item which store weight and corresponding
// value of Item
struct Item
{
int value, weight;
// Constructor
Item(int value, int weight) : value(value), weight(weight)
{}
};
// Comparison function to sort Item according to val/weight ratio
bool cmp(struct Item a, struct Item b)
{
double r1 = (double)a.value / a.weight;
double r2 = (double)b.value / b.weight;
return r1 > r2;
}
// Main greedy function to solve problem
double fractionalKnapsack(int W, struct Item arr[], int n)
{
// sorting Item on basis of ration
sort(arr, arr + n, cmp);
// Uncomment to see new order of Items with their ratio
/*
for (int i = 0; i < n; i++)
{
cout << arr[i].value << " " << arr[i].weight << " : "
<< ((double)arr[i].value / arr[i].weight) << endl;
}
*/
int curWeight = 0; // Current weight in knapsack
double finalvalue = 0.0; // Result (value in Knapsack)
// Looping through all Items
for (int i = 0; i < n; i++)
{
// If adding Item won't overflow, add it completely
if (curWeight + arr[i].weight <= W)
{
curWeight += arr[i].weight;
finalvalue += arr[i].value;
}
// If we can't add current Item, add fractional part of it
else
{
int remain = W - curWeight;
finalvalue += arr[i].value * ((double) remain / arr[i].weight);
break;
}
}
// Returning final value
return finalvalue;
}
// driver program to test above function
int main()
{
int W = 50; // Weight of knapsack
Item arr[] = {{60, 10}, {100, 20}, {120, 30}};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum value we can obtain = "
<< fractionalKnapsack(W, arr, n);
return 0;
}
Explanation / Answer
I have translated the same code to java. Most of the code is similar to provided c++ except the sorting procedure.We used "Comparator" function to sort the array of object based on the ratio. Have a look at below statement to see how we used Comparator method
Arrays.sort(arr, Item.itemComparator);
Java Code:
import java.util.Arrays;
import java.util.Comparator;
//This class is equivalent to struct Item
class Item implements Comparable<Item> {
int value, weight;
public Item(int value, int weight) {
this.value = value;
this.weight = weight;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
//These methods will help in Sorting the array of items according to the ratio
@Override
public int compareTo(Item b) {
double r1 = (double) this.value / this.weight;
double r2 = (double) b.value / b.weight;
return (int) (r1 - r2);
}
public static Comparator<Item> itemComparator = new Comparator<Item>() {
public int compare(Item a, Item b) {
return b.compareTo(a);
}
};
}
class Knapsack {
// Main greedy function to solve the problem
static double fractionalKnapsack(int W, Item arr[], int n) {
// sorting Item on basis of ration
Arrays.sort(arr, Item.itemComparator);
// Uncomment to see new order of Items with their ratio
/*
* for (int i = 0; i < n; i++)
*
* {
*
* System.out.println(arr[i].value + " " + arr[i].weight + " : "+
* ((double)arr[i].value / arr[i].weight) );
*
*
* }
*
*/
int curWeight = 0; // Current weight in knapsack
double finalvalue = 0.0; // Result (value in Knapsack)
// Looping through all Items
for (int i = 0; i < n; i++)
{
// If adding Item won't overflow, add it completely
if (curWeight + arr[i].weight <= W)
{
curWeight += arr[i].weight;
finalvalue += arr[i].value;
}
// If we can't add current Item, add fractional part of it
else
{
int remain = W - curWeight;
finalvalue += arr[i].value * ((double) remain / arr[i].weight);
break;
}
}
// Returning final value
return finalvalue;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int W = 50; // Weight of knapsack
Item arr[] = { new Item(60, 10), new Item(100, 20), new Item(120, 30) };
int n = arr.length;
System.out.println("Maximum value we can obtain = " + fractionalKnapsack(W, arr, n));
}
}
Output:
Maximum value we can obtain = 240.0
I hope I could solve your problem.Further if you have any doubt, please ask.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.