Scribd
Upload
7 views4 pages

Knapsack Problem: Dynamic & Greedy Methods

The document discusses two algorithms for solving the knapsack problem: dynamic programming and the greedy method. The dynamic programming approach has a time and space complexity of O(n⋅W), while the greedy method has a time complexity of O(n log n) and uses O(1) extra space. Both methods include detailed algorithms and source code examples in C.

Uploaded by

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

Knapsack Problem: Dynamic & Greedy Methods

The document discusses two algorithms for solving the knapsack problem: dynamic programming and the greedy method. The dynamic programming approach has a time and space complexity of O(n⋅W), while the greedy method has a time complexity of O(n log n) and uses O(1) extra space. Both methods include detailed algorithms and source code examples in C.

Uploaded by

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

Brijendra Srivastava

2300290110066

CSIT 5A

Q. knapsack problem

a. Dynamic programming

Algorithm

1. Input:

 n items, each with value val[i] and weight wt[i]

 Knapsack capacity W

2. Define:

 dp[i][w] = maximum value for first i items and capacity w

3. Base Case:

 For i=0 or w=0: dp[i][w]=0

4. Recurrence:

 If wt[i-1] > w: dp[i][w] = dp[i-1][w]

 Else: dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w-wt[i-1]])

5. Answer:

 dp[n][W] is the maximum profit

source code

#include <stdio.h>

int max(int a, int b) { return (a > b)? a : b; }

int knapSack(int W, int wt[], int val[], int n) {

int i, w;

int K[n+1][W+1];

for (i = 0; i <= n; i++) {

for (w = 0; w <= W; w++) {

if (i==0 || w==0)

K[i][w] = 0;

else if (wt[i-1] <= w)

K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);


else

K[i][w] = K[i-1][w];

return K[n][W];

int main() {

int val[] = {60, 100, 120};

int wt[] = {10, 20, 30};

int W = 50;

int n = sizeof(val)/sizeof(val[0]);

printf("Maximum value in knapsack = %d\n", knapSack(W, wt, val, n));

return 0;

Output

complexity

 Time complexity: O(n⋅W)O(n⋅W)


(nn = number of items, WW = knapsack capacity)

 Space complexity: O(n⋅W)O(n⋅W) (can be optimized to O(W)O(W) using 1D array)

b. greedy method

algorithm

1. Input:

 Items with value val[i] and weight wt[i]

 Knapsack capacity W

2. Compute:

 Value/weight ratio for each item

3. Sort:
 Sort items in descending order of value/weight ratio

4. Pick:

 For each item:

 If the item fits, take the whole item

 Else, take the fraction that fits to fill the knapsack

5. Output:

 Sum the total value selected

Source code

#include <stdio.h>

struct Item {

int value, weight;

};

void swap(struct Item* a, struct Item* b) {

struct Item t = *a;

*a = *b;

*b = t;

void sortItems(struct Item items[], int n) {

for(int i=0;i<n-1;i++)

for(int j=0;j<n-i-1;j++)

if((float)items[j].value/items[j].weight < (float)items[j+1].value/items[j+1].weight)

swap(&items[j], &items[j+1]);

float fractionalKnapsack(int W, struct Item items[], int n) {

sortItems(items, n);

float totalValue = 0.0;

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

if (items[i].weight <= W) {

W -= items[i].weight;

totalValue += items[i].value;
} else {

totalValue += items[i].value * ((float)W / items[i].weight);

break;

return totalValue;

int main() {

struct Item items[] = {{60, 10}, {100, 20}, {120, 30}};

int n = sizeof(items)/sizeof(items[0]);

int W = 50;

float maxValue = fractionalKnapsack(W, items, n);

printf("Maximum value in Fractional Knapsack = %.2f\n", maxValue);

return 0;

Output

Complexity

 Time complexity: O(nlogn)O(nlogn) (for sorting)

 Space complexity: O(1)O(1) extra space apart from input

You might also like