Knapsack Using Greedy Algorithm
Code:
package com.nearur;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class KNAPSACK {
static int capacity=40;
public static void main(String[] args) {
package com.nearur;
public class Item {
String name;
int value,weight;
public Item(String name, int value, int weight) {
super();
this.name = name;
this.value = value;
this.weight = weight;
}
int compareWeight(Item x) {
if(x.weight>weight) {
return -1;
}return 1;
}
int compareValue(Item x) {
if(x.value>value) {
return 1;
}return -1;
}
int compareratio(Item x) {
if(x.value/x.weight>value/weight) {
return 1;
}return -1;
}
}
Item [] item=new Item[4];
item[0]=new Item("I1",100,20);
item[1]=new Item("I2",90,10);
item[2]=new Item("I3",40,15);
item[3]=new Item("I4",50,5);
ArrayList<Item> knapsack=new ArrayList<>();
ArrayList<Item> allitems=new ArrayList<>();
for(int i=0;i<item.length;i++) {
allitems.add(item[i]);
}
Comparator<Item> com=new Comparator<Item>() {
@Override
public int compare(Item o1, Item o2) {
return o1.compareratio(o2);
//return o1.compareValue(o2);
//return o1.compareWeight(o2);
}
};
Collections.sort(allitems,com);
for(Item ite:allitems) {
System.out.println(ite.name);
if(ite.weight<=capacity) {
knapsack.add(ite);
capacity=capacity-ite.weight;
}
}
int mvalue=0,mweight=0;
for(Item i: knapsack) {
mvalue +=i.value;
mweight +=i.weight;
}
System.out.println("Total Value: "+mvalue+"\nTotal Weight: "+mweight);
}
}
Output:
