[go: up one dir, main page]
Scribd
Upload
10 views4 pages

Alghorith Lab 4

Uploaded by

stayoutoffire
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
10 views4 pages

Alghorith Lab 4

Uploaded by

stayoutoffire
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/ 4

Green University of Bangladesh

Department of Computer Science and Engineering (CSE)


Faculty of Sciences and Engineering Semester: (FALL, Year:2024), B.Sc. in
CSE (Day)

Lab Report 04

Course Title: Alghorithm


Code: CSE 206
Section: 222 D9

Lab Experiment Name : 0 1 Knapsack Problem Also Selected Item


.

Student Details

Name ID

Shariful Islam Shazid 221902089

Submission Date: 14/05/2024


Course Teacher’s Name: Mr. Mozdaher Abdul Quader
[For Teachers use only: Don’t Write Anything inside this box]

1.Experiment name :

• 0 - 1 knapsack problem

2. Objective :
This Java code aims to solve the 0-1 Knapsack Problem using dynamic programming. Given a set of
items with associated values and weights, and a maximum weight capacity for a knapsack, the objective
is to determine the maximum value of items that can be placed into the knapsack without exceeding its
capacity. Additionally, the code identifies which specific items are selected for inclusion in the knapsack
to achieve the maximum value..

3. PROCEDURE / ANALYSIS / DESIGN:

• 0-1 Knapsack :

The code sets up a dynamic programming table to store optimal solutions, iterates through each item
and weight combination to compute the maximum value achievable, and backtracks to determine the
selected items. Finally, it returns the maximum value and prints the selected items along with their
values and weights, solving the 0-1 Knapsack Problem.

3. Implementation :

 0-1 Knapsack Also The Selected Item :


import java.util.ArrayList;

class Knapsack {
public static int knapSack(int W, int wt[], int val[], int n,
ArrayList<Integer> selectedItems) { int[][] dp = new
int[n+1][W+1];

// Build table dp[][] in bottom-up manner


for (int i = 0; i <= n; i++)
{ for (int w = 0; w <= W;
w++) { if (i == 0 || w ==
0) dp[i][w] = 0;
else if (wt[i-1] <= w)
dp[i][w] = Math.max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-
1][w]);
else
dp[i][w] = dp[i-1][w];
}
}

int w = W;
for (int i = n; i > 0 && dp[i][w] > 0; i--)
{ if (dp[i][w] != dp[i-1][w])
{ selectedItems.add(i-1);
w -= wt[i-1];
}
}

return dp[n][W];
}
}
public class Main {

public static void main(String args[])


{ int val[] = {60, 100, 120};
int wt[] = {10, 20, 30}; int W =
50;
int n = val.length;
ArrayList<Integer> selectedItems = new ArrayList<>();

int maxValue = Knapsack.knapSack(W, wt, val, n, selectedItems);


System.out.println("Maximum value that can be attained is " + maxValue);
System.out.println("Selected items:");
for (int i = selectedItems.size() - 1; i >= 0; i--) {
System.out.println("Item " + (selectedItems.get(i) + 1) + " (value: "
+ val[selectedItems.get(i)] + ", weight: " + wt[selectedItems.get(i)] + ")");
}
}
}
}

OUTPUT:

DISCUSSION

This Java implementation effectively solves the 0-1 knapsack problem using dynamic
programming. It iterates through all items and weights together to calculate the maximum price,
effectively handling restrictions like item weight and baggage allowance. It is also possible to
determine the product options that provide the highest profit by backtracking. The code provides
flexible and scalable solutions to knapsack problems, suitable for many optimization tasks.

You might also like