Implement 0/1 Knapsack problem using Greedy method

Overview of the 0/1 Knapsack Problem

The 0/1 Knapsack Problem involves selecting items to maximize their total value without exceeding a given weight capacity. Each item has a specific weight and value, and the goal is to determine the maximum total value of items that can fit in the knapsack.

import java.util.Scanner;
public class knapsacgreedy {
/**
* @param args
*/
public static void main(String[] args) {
int i,j=0,max_qty,m,n;
float sum=0,max;
Scanner sc = new Scanner(System.in);
int array[][]=new int[2][20];
System.out.println("Enter no of items");
n=sc.nextInt();
System.out.println("Enter the weights of each items");
for(i=0;i<n;i++)< span="">
array[0][i]=sc.nextInt();
System.out.println("Enter the values of each items");
for(i=0;i<n;i++)< span="">
array[1][i]=sc.nextInt();
System.out.println("Enter maximum volume of knapsack :");
max_qty=sc.nextInt();
m=max_qty;
while(m>=0)
{
max=0;
for(i=0;i<n;i++)< span="">
{
if(((float)array[1][i])/((float)array[0][i])>max)
{
max=((float)array[1][i])/((float)array[0][i]);
j=i;
}
}
if(array[0][j]>m)
{
System.out.println("Quantity of item number: "+ (j+1) + " added is " +m);
sum+=m*max;
m=-1;
}
else
{
System.out.println("Quantity of item number: " + (j+1) + " added is " + array[0][j]);
m-=array[0][j];
sum+=(float)array[1][j];
array[1][j]=0;
}

}
System.out.println("The total profit is " + sum);
sc.close();
}
}</n;i++)<></n;i++)<></n;i++)<>

Code Breakdown

Imports and Class Declaration:

import java.util.Scanner;

public class knapsacgreedy {

The Scanner class is imported to facilitate user input.
The class is defined as knapsacgreedy.

Main Method:

public static void main(String[] args) {

The main method serves as the entry point of the program.

Variable Declarations:

int i,j=0,max_qty,m,n;
float sum=0,max;

i and j are used for iteration.
max_qty holds the maximum weight capacity of the knapsack.
m is a variable to track the remaining capacity of the knapsack.
n is the number of items being considered.
sum is used to accumulate the total value of the items added to the knapsack.
max stores the maximum value-to-weight ratio during the selection process.

Scanner Initialization:

Scanner sc = new Scanner(System.in);

A Scanner object sc is instantiated to read input from the user.

Array Initialization:

int array[][]=new int[2][20];

A 2D array named array is created to store weights and values of the items. The first row (array[0]) holds the weights, and the second row (array[1]) holds the values.

User Input for Items:

System.out.println("Enter no of items");
n=sc.nextInt();
System.out.println("Enter the weights of each items");
for(i=0;i<n;i++)
array[0][i]=sc.nextInt();
System.out.println("Enter the values of each items");
for(i=0;i<n;i++)
array[1][i]=sc.nextInt();

The user is prompted to input the number of items (n).
The program collects weights and values for each item and stores them in the respective rows of the array.

Input for Maximum Knapsack Capacity:

System.out.println("Enter maximum volume of knapsack :");
max_qty=sc.nextInt();
m=max_qty;

The user is asked to input the maximum capacity of the knapsack. This value is stored in max_qty and copied to m.

Main Loop for Selecting Items:

while(m>=0) {
max=0;
for(i=0;i<n;i++) {
if(((float)array[1][i])/((float)array[0][i])>max) {
max=((float)array[1][i])/((float)array[0][i]);
j=i;
}
}

The loop continues until there is no remaining capacity (m < 0).
A nested loop iterates over each item to find the item with the highest value-to-weight ratio. The index of this item is stored in j.

Adding Items to the Knapsack:

if(array[0][j]>m) {
System.out.println("Quantity of item number: "+ (j+1) + " added is " +m);
sum+=m*max;
m=-1;
} else {
System.out.println("Quantity of item number: " + (j+1) + " added is " + array[0][j]);
m-=array[0][j];
sum+=(float)array[1][j];
array[1][j]=0;
}

If the weight of the selected item (at index j) exceeds the remaining capacity (m), only a fraction of that item can be added to the knapsack (though this is incorrect for 0/1 Knapsack).
If the item can be fully added to the knapsack, its weight is subtracted from m, and its value is added to sum. The value of the item in the array is set to zero to indicate that it has been fully utilized.

System.out.println("The total profit is " + sum);
sc.close();

Limitations

Greedy Method for 0/1 Knapsack: The greedy algorithm used here is not suitable for the 0/1 Knapsack problem. In 0/1 Knapsack, an item cannot be divided; it must be either included completely or excluded. This code doesn’t enforce that, leading to potentially incorrect results.
No Sorting or Index Management: There is no sorting of items based on their value-to-weight ratio, which is crucial in a proper greedy approach.

Output:
Enter no of items
4
Enter the weights of each items
2132
Enter the values of each items
12
10
20
15
Enter maximum volume of knapsack :
5
Quantity of item number: 2 added is 1
Quantity of item number: 4 added is 2
Quantity of item number: 3 added is 2
The total profit is 38.333332