The code gives correct output. How do I calculate time complexity for code like this?
The program finds all the combinations of items and sees if the combination gives the max profit. If the last item can't be added or there are no more items left, it checks to see if this value of knapsack is maximum or not.
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class Item {
static int id = 0;
int weight;
int cost;
double ratio;
int itemNo = id++;
public Item(int weight, int cost) {
this.weight = weight;
this.cost = cost;
this.ratio = (double) cost / weight;
}
public String toString() {
return itemNo + "";
}
}
class Store {
int nItems;
List<Item> store = new ArrayList<>();
Item getNextHighestRatioItem() {
int i = -1;
double highestRatio = Double.MIN_VALUE;
for (int j = 0; j < store.size(); ++j) {
double thisRatio = store.get(j).ratio;
if (thisRatio > highestRatio) {
i = j;
highestRatio = thisRatio;
}
}
return store.get(i);
}
}
class Knapsack {
Knapsack(int nItems, int maxWeight) {
this.maxWeight = maxWeight;
this.knapsack = new boolean[nItems];
}
boolean[] knapsack;
int maxWeight = 50;
int weight;
int worth;
public boolean addItem(Item item) {
if (weight + item.weight > maxWeight) {
return false;
}
knapsack[item.itemNo] = true;
weight += item.weight;
worth += item.cost;
return true;
}
public void removeItem(Item item) {
knapsack[item.itemNo] = false;
weight = weight - item.weight;
worth -= item.cost;
}
public boolean isFull() {
return weight == maxWeight;
}
}
public class Knapsack01 {
int knapsackCapacity, nItems;
Store storeInstance;
Knapsack knapsackInstance;
Scanner scan = new Scanner(System.in);
Knapsack01() {
System.out.println("Enter the size of the knapsack ");
knapsackCapacity = scan.nextInt();
storeInstance = new Store();
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of items: ");
nItems = scan.nextInt();
int weight, cost, ratio;
for (int i = 0; i < nItems; ++i) {
System.out.println("Enter item " + (i + 1) + "'s weight and cost: ");
weight = scan.nextInt();
cost = scan.nextInt();
Item item = new Item(weight, cost);
storeInstance.store.add(item);
}
knapsackInstance = new Knapsack(nItems, knapsackCapacity);
}
public void printSolution(int runningMax) {
System.out.println("\nFound a better solution, worth : " + runningMax + "\nItems: ");
//Print knapsack contents
for (int j = 0; j < knapsackInstance.knapsack.length; ++j) {
if (knapsackInstance.knapsack[j] == true) {
System.out.print((j + 1) + " ");
}
}
}
int runningMax = 0;
public void combinations(int callingIndex) {
for (int i = callingIndex; i < knapsackInstance.knapsack.length; ++i) {
if (knapsackInstance.knapsack[i] == true) {
continue;
}
if (knapsackInstance.addItem(storeInstance.store.get(i))) {
combinations(i);
//Check worth only if the item has been added and it is the last item [no more items to add]
if (i == knapsackInstance.knapsack.length - 1) {
if (knapsackInstance.worth > runningMax) {
runningMax = knapsackInstance.worth;
printSolution(runningMax);
}
knapsackInstance.removeItem(storeInstance.store.get(i));
return;
}
knapsackInstance.removeItem(storeInstance.store.get(i));
} else { //or if the next item couldn't be added as the knapsack was already full
if (knapsackInstance.worth >= runningMax) {
runningMax = knapsackInstance.worth;
printSolution(runningMax);
}
}
}
}
public static void main(String[] args) {
Knapsack01 kp = new Knapsack01();
kp.combinations(0);
}
}