import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class KnappsackProblem {
private static int K = 0;
private static int N = 0;
public static void main(String[] args) {
String file = "example.txt";
Element [] arr = readInstances("Directory To Instances" + file);//new Element[N];
System.out.println(knapsack(K, arr));
}
private static int knapsack(int capacity, Element[] arr) {
TreeNode elem = new TreeNode(0, 0, null, 0, 0.0, null);
Arrays.sort(arr, new ElementComparator());
elem.items = arr;
int weight = 0;
int numberFit = 0;
double upperBound = 0;
double lowerBound = 0;
while(weight <= capacity) {
if((weight + arr[0].weight) <= capacity) {
upperBound += arr[0].value;
weight += arr[0].weight;
numberFit++;
}else {
break;
}
}
UpperBound bound = new UpperBound((int) upperBound, 0, weight, 0);
double percent = (capacity-weight)/arr[0].weight;
upperBound += arr[0].value*percent;
weight += arr[0].weight*percent;
lowerBound = arr[0].value*numberFit;
elem.lowerBound = (int) lowerBound;
bound.filledBound = (int) Math.ceil(upperBound);
bound.filledBoundWeight = weight;
elem.upperBound = bound;
return knapsackSolver(elem, capacity);
}
private static int knapsackSolver(TreeNode elem, int capacity) {
if(elem.lowerBound > elem.upperBound.filledBound) {
System.out.println(elem);
System.out.println("Youre a bitch...Pruned by Bound!");
return 0;
}
if(elem.profit > elem.upperBound.filledBoundWeight) {
System.out.println(elem);
System.out.println("Bitch goodbye...Pruned by Infeasability");
return 0;
}
if(elem.upperBound.filledBound == elem.lowerBound) {
System.out.println("Optimal Result");
return elem.lowerBound;
}
TreeNode[] arr = new TreeNode[elem.items.length*2];
int indexer = 0;
for(int i = 0; i < elem.items.length; i++) {
UpperBound boundIn = findBound(i, capacity, elem.profit + elem.items[i].value,
elem.weight + elem.items[i].weight, true, elem.items, elem.upperBound);
TreeNode in = new TreeNode(elem.level + 1,
elem.profit + elem.items[i].value,
boundIn,
boundIn.normalBound,
elem.weight + elem.items[i].weight,
elem.items);
Element[] itemsArr = new Element[elem.items.length-1];
for(int j = 0, k = 0; j < elem.items.length; j++) {
if(j != i) {
itemsArr[k] = elem.items[j];
k++;
}
}
UpperBound boundOut = findBound(i, capacity, elem.profit, elem.weight, false, itemsArr, elem.upperBound);
TreeNode out = new TreeNode(elem.level + 1,
elem.profit,
boundOut,
boundOut.normalBound,
elem.weight,
itemsArr);
arr[indexer] = in;
arr[indexer+1] = out;
indexer += 2;
}
Arrays.sort(arr, new TreeNodeComparator());
int var = 0;
int result = 0;
for(int i = 0; i < arr.length; i++) {
result = knapsackSolver(arr[i], capacity);
var += result > var ? result : 0;
}
return var;
}
private static UpperBound findBound(int item, int capacity, int profit, double inputWeight, boolean bounding, Element[] arr, UpperBound oldBound) {
double value = profit;
double weight = inputWeight;
if(arr.length > 0) {
if(bounding){
value += arr[item].value;
weight += arr[item].weight;
}
UpperBound result = new UpperBound((int) value, 0, weight, 0);
double percent = (capacity-weight)/arr[0].weight;
System.out.println("Percent: " + percent);
value = Math.ceil(value + (arr[0].value*percent));
weight = Math.ceil(weight + (arr[0].weight*percent));
result.filledBound = (int) value;
result.filledBoundWeight = (int) weight;
return result;
}
return oldBound;
}
@SuppressWarnings("resource")
private static Element [] readInstances(String filepath) {
try{
File s = new File(filepath);
BufferedReader in = new BufferedReader(new FileReader(s));
ArrayList<Element> list = new ArrayList<>();
String temp = "";
temp = in.readLine();
String [] part = temp.split(" ");
N = Integer.parseInt(part[0]);
K = Integer.parseInt(part[1]);
int weight = 0;
int value = 0;
while((temp = in.readLine()) != null) {
part = temp.split(" ");
weight = Integer.parseInt(part[0]);
value = Integer.parseInt(part[1]);
list.add(new Element(weight, value));
}
return convertListToArray(list);
}catch(NumberFormatException|IOException ex){
ex.printStackTrace();
}
return null;
}
private static Element[] convertListToArray(ArrayList<Element> list) {
Element[] result = new Element[list.size()];
for(int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
}
class ElementComparator implements Comparator<Element>{
@Override
public int compare(Element o1, Element o2) {
if (!(o1 instanceof Element) || !(o2 instanceof Element))
throw new ClassCastException();
Element item1 = (Element) o1;
Element item2 = (Element) o2;
double value1 = (double) item1.value/item1.weight;
double value2 = (double) item2.value/item2.weight;
if(value1 < value2) return 1;
else if(value1 > value2) return -1;
return 0;
}
}
class TreeNodeComparator implements Comparator<TreeNode>{
@Override
public int compare(TreeNode o1, TreeNode o2) {
if (!(o1 instanceof TreeNode) || !(o2 instanceof TreeNode))
throw new ClassCastException();
TreeNode item1 = (TreeNode) o1;
TreeNode item2 = (TreeNode) o2;
if(item1.profit > item2.profit) return -1;
else if(item1.profit < item2.profit) return 1;
return 0;
}
}
class Element{
public double weight;
public int value;
public Element(double weight, int value) {
this.weight = weight;
this.value = value;
}
public String toString() {
return "(Weigth: " + weight + ", Value: " + value + ")";
}
}
class UpperBound{
public int normalBound;
public int filledBound;
public double normalBoundWeight;
public double filledBoundWeight;
public UpperBound(int normalBound, int filledBound, double normalBoundWeight, double filledBoundWeight) {
this.normalBound = normalBound;
this.filledBound = filledBound;
this.normalBoundWeight = normalBoundWeight;
this.filledBoundWeight = filledBoundWeight;
}
public String toString() {
return "(Normal Bound: " + this.normalBound + ", Weight: " + this.normalBoundWeight
+ " | Filled Bound: " + this.filledBound
+ ", Weight: " + this.filledBoundWeight + ")";
}
}
class TreeNode {
public int level;
public int profit;
public UpperBound upperBound;
public int lowerBound;
public double weight;
public Element[] items;
public TreeNode(int level, int profit, UpperBound upperBound, int lowerBound, double weight, Element[] items) {
this.level = level;
this.profit = profit;
this.upperBound = upperBound;
this.lowerBound = lowerBound;
this.weight = weight;
this.items = items;
}
public TreeNode(TreeNode old) {
this.level = old.level;
this.profit = old.profit;
this.upperBound = old.upperBound;
this.lowerBound = old.lowerBound;
this.weight = old.weight;
this.items = old.items;
}
public String toString() {
return "(Level: " + level + ", Profit: " + profit + ", Lower Bound: " + lowerBound + ", Upper Bound: " + upperBound + ", Weight: " + weight + ")";
}
}
