Scribd
Upload
7 views5 pages

Knapsack

The document contains a Java implementation of a greedy algorithm for the dynamic knapsack problem. It includes methods for reading item weights and profits, calculating the profit-to-weight ratio, and selecting items based on this ratio to maximize profit within a given weight limit. The solution vector and total profit are printed as output after the calculations.

Uploaded by

DEVEDANANDA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views5 pages

Knapsack

The document contains a Java implementation of a greedy algorithm for the dynamic knapsack problem. It includes methods for reading item weights and profits, calculating the profit-to-weight ratio, and selecting items based on this ratio to maximize profit within a given weight limit. The solution vector and total profit are printed as output after the calculations.

Uploaded by

DEVEDANANDA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

import java.util.

Scanner;

class MyDynamicKnapsack {
int n, M;
int w[], p[];

void greedySack() {
double sum = 0;
double ratio[] = new double[n + 1];
double sol[] = new double[n + 1];

for (int i = 1; i <= n; i++) {


ratio[i] = (double) p[i] / w[i];
// profit to weight ratio
}

for (int q = 1; q <= n; q++) {


double max = 0.0;
int k = 0; // to store max ratio index
for (int i = 1; i <= n; i++) {
if ((ratio[i] > max) && (sol[i] == 0)) {
max = ratio[i];
k = i;
}
}

if (M > 0) {

if (M >= w[k]) {
sol[k] = 1; // selected
M = M - w[k];
sum = sum + p[k];
}

else {
double r = (double) M / w[k];
sol[k] = r; // selected
sum = sum + (r * p[k]);
M = 0;
}

} else {
sol[k] = -1; // cannot select
}
}

for (int i = 1; i <= n; i++) {


if (sol[i] == -1)
sol[i] = 0;
}

System.out.println("\nSolution with Greedy Method: " +


sum);
System.out.print("The solution vector is:");
for (int i = 1; i <= n; i++)
System.out.print(" " + sol[i]);
}

void read() {
Scanner s = new Scanner(System.in);

System.out.print("Enter num of items: ");


n = s.nextInt();
w = new int[n + 1]; // weight
p = new int[n + 1]; // profit
System.out.print("Enter Knapsack size: ");
M = s.nextInt();

System.out.println("Enter Weights of all Items");


for (int i = 1; i <= n; i++) {
w[i] = s.nextInt();
}

System.out.println("Enter Profits of all Items");


for (int i = 1; i <= n; i++) {
p[i] = s.nextInt();
}
}

public class DynamicKnapsack {

public static void main(String[] args) {


// TODO Auto-generated method stub
MyDynamicKnapsack MDK = new MyDynamicKnapsack();
MDK.read();
MDK.greedySack();
}

You might also like