Knapsack problems are those problems in which some set of items will be given to us, each with a weight and value and we will be asked to find the most valuable combination by maximizing the total value of items and the weight should not exceed the knapsack weigh.
Approximation Algorithms:
It plays a vital role in finding the optimal solution to the knapsack problems as in real-world scenarios finding the exact optimal solution to the knapsack problem is quite impractical due to the problem’s NP-hard nature. These approximation algorithms offer a reasonable solution to the knapsack problem by taking both time and space complexity into consideration.
we will discuss two approximation algorithms:
Let’s consider a problem statement to understand these algorithms better:
Given a set of items, each with a weight and a value, and a knapsack of limited capacity, we need to find the most valuable combination of items to include in the knapsack while ensuring that the total weight does not exceed the knapsack’s capacity.
Examples:
Input: N = 3, W = 4, values[] = {1, 2, 3}, weight[] = {4, 5, 1}
Output: 3
Explanation: In this example, we have three items with respective values and weights:
- Item 1: value = 1, weight = 4
- Item 2: value = 2, weight = 5
- Item 3: value = 3, weight = 1
The knapsack has a capacity of 4. By selecting either Item 1 or Item 3, we can achieve the maximum value of 3. Since the weight of Item 1 (4) exceeds the knapsack’s capacity, we choose Item 3, which has a weight of 1 and a value of 3.
Input: N = 3, W = 3, values[] = {1, 2, 3}, weight[] = {4, 5, 6}
Output: 0
Greedy Algorithms to the Knapsack Problem
The greedy approach is a simple and intutive algorithm for solving knapsack problem. It will select the items based on theri value to weight ratios and choosing the items with highest ratios first.
Step-by-step algorithm:
- Sort the items in descending order of their value-to-weight ratios.
- Initialize the knapsack as empty and set the total value to zero.
- Iterate through the items in the sorted order:
- If the current item can be fully included in the knapsack, add it completely and update the total value.
- Otherwise, include a fractional part of the item that fits the remaining capacity of the knapsack, proportionally increasing the total value.
- Return the knapsack’s final configuration and the total value.
Below is the implementation of the above approach in Python:
C++
// CPP program of the above approach#include <bits/stdc++.h>using namespace std;struct Item { double ratio; int index;};bool compare(Item a, Item b) { return a.ratio > b.ratio; }int knapsack_greedy(int N, int W, vector<int>& values, vector<int>& weights){ vector<Item> ratios(N); // Calculate value-to-weight ratios for all items for (int i = 0; i < N; i++) { ratios[i].ratio = static_cast<double>(values[i]) / weights[i]; ratios[i].index = i; } sort(ratios.begin(), ratios.end(), compare); int total_value = 0; int total_weight = 0; for (const auto& item : ratios) { int index = item.index; if (total_weight + weights[index] <= W) { total_value += values[index]; total_weight += weights[index]; } } return total_value;}// Driver's Codeint main(){ int N = 3; int W = 4; vector<int> values = { 1, 2, 3 }; vector<int> weights = { 4, 5, 1 }; int result = knapsack_greedy(N, W, values, weights); cout << result << endl; return 0;}// This code is contributed by Susobhan Akhuli |
Java
// Java program of the above approachimport java.util.*;class Item { double ratio; int index;}public class GFG { // Custom comparator to sort items based on the // value-to-weight ratio in descending order static class ItemComparator implements Comparator<Item> { public int compare(Item a, Item b) { return Double.compare(b.ratio, a.ratio); } } static int knapsackGreedy(int N, int W, int[] values, int[] weights) { // Create an array to store items with their // corresponding value-to-weight ratio Item[] items = new Item[N]; for (int i = 0; i < N; i++) { items[i] = new Item(); items[i].ratio = (double)values[i] / weights[i]; items[i].index = i; } // Sort the items based on the value-to-weight ratio // in descending order Arrays.sort(items, new ItemComparator()); int totalValue = 0; int totalWeight = 0; // Iterate through the sorted items and add them to // the knapsack if possible for (Item item : items) { int index = item.index; if (totalWeight + weights[index] <= W) { totalValue += values[index]; totalWeight += weights[index]; } } return totalValue; } // Driver's Code public static void main(String[] args) { int N = 3; int W = 4; int[] values = { 1, 2, 3 }; int[] weights = { 4, 5, 1 }; int result = knapsackGreedy(N, W, values, weights); System.out.println(result); }}// This code is contributed by Susobhan Akhuli |
Python3
def knapsack_greedy(N, W, values, weights): # Calculate value-to-weight ratios for all items ratios = [(values[i] / weights[i], i) for i in range(N)] ratios.sort(reverse=True) total_value = 0 total_weight = 0 for ratio, item in ratios: if total_weight + weights[item] <= W: total_value += values[item] total_weight += weights[item] return total_value# Example usageN = 3W = 4values = [1, 2, 3]weights = [4, 5, 1]result = knapsack_greedy(N, W, values, weights)print(result) |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;using System.Linq;class Item{ public double Ratio { get; set; } public int Index { get; set; }}public class GFG{ // Custom comparator to sort items based on the // value-to-weight ratio in descending order class ItemComparer : IComparer<Item> { public int Compare(Item a, Item b) { return b.Ratio.CompareTo(a.Ratio); } } static int KnapsackGreedy(int N, int W, int[] values, int[] weights) { // Create an array to store items with their // corresponding value-to-weight ratio Item[] items = new Item[N]; for (int i = 0; i < N; i++) { items[i] = new Item { Ratio = (double)values[i] / weights[i], Index = i }; } // Sort the items based on the value-to-weight ratio // in descending order Array.Sort(items, new ItemComparer()); int totalValue = 0; int totalWeight = 0; // Iterate through the sorted items and add them to // the knapsack if possible foreach (Item item in items) { int index = item.Index; if (totalWeight + weights[index] <= W) { totalValue += values[index]; totalWeight += weights[index]; } } return totalValue; } // Driver's Code public static void Main(string[] args) { int N = 3; int W = 4; int[] values = { 1, 2, 3 }; int[] weights = { 4, 5, 1 }; int result = KnapsackGreedy(N, W, values, weights); Console.WriteLine(result); }}// This is contributed by Sakshi |
Javascript
function GFG(N, W, values, weights) { const ratios = []; // Calculate value-to-weight ratios // for all items for (let i = 0; i < N; i++) { const ratio1 = values[i] / weights[i]; ratios.push({ ratio1, index: i }); } // Sort the ratios array in // descending order based on ratios ratios.sort((a, b) => b.ratio1 - a.ratio1); let totalValue = 0; let totalWeight = 0; // Iterate through the sorted ratios array for (const item of ratios) { const index = item.index; // Check if adding the current item's weight exceeds // the knapsack capacity if (totalWeight + weights[index] <= W) { totalValue += values[index]; totalWeight += weights[index]; } } return totalValue;}// Mainfunction main() { const N = 3; const W = 4; const values = [1, 2, 3]; const weights = [4, 5, 1]; const result = GFG(N, W, values, weights); console.log(result);}main(); |
Output
3
Time Complexity: O(N log N) where N is the number of items due to sorting
Auxiliary Space: O(N) where N is the number of items.
Dynamic Programming Approach for the Knapsack Problem
Using dynamic programming we can break down the problem into smaller subproblems and will use a table to store the optimal solutions for the these subproblems. We will iterate through each item and weight combination making a decision to either include or exclude the item based on its value and weight and we can achieve result by avoiding redundant calucations
Step-by-step algorithm:
- Create a 2D list called dp with dimensions (N+1) x (W+1) and initialize all values to 0. This table will store the maximum achievable values for different combinations of items and capacities.
- Iterate through each item from 1 to N and each capacity from 1 to W:
- If the weight of the current item is greater than the current capacity, it cannot be included in the knapsack. So, assign the value at the previous item and the same capacity to dp[i][j].
- If the weight of the current item is less than or equal to the current capacity, we have two choices:
- Include the current item: Add its value to the value obtained by considering the remaining capacity after including the item (values[i-1] + dp[i-1][j – weights[i-1]]).
- Exclude the current item: Consider the value obtained by excluding the item (dp[i-1][j]). Choose the maximum value between the two choices and assign it to dp[i][j].
- After completing the iterations, the value at dp[N][W] represents the maximum achievable value for the given knapsack capacity.
- Return the value dp[N][W] as the maximum value that can be obtained.
Below is the implementation for the above approach:
C++
// CPP code of the above approach#include <bits/stdc++.h>using namespace std;// Function to solve the knapsack problemint knapsack(int N, int W, vector<int> values, vector<int> weights){ // Initializing a 2D vector for dynamic programming vector<vector<int> > dp(N + 1, vector<int>(W + 1, 0)); // Loop through the items for (int i = 1; i < N + 1; i++) { // Loop through the weight capacity for (int j = 1; j < W + 1; j++) { // Check if the current item's weight exceeds // the capacity if (weights[i - 1] > j) { // If the weight is greater, take the value // without this item dp[i][j] = dp[i - 1][j]; } else { // If the weight is feasible, find the // maximum value considering whether to take // this item dp[i][j] = max( values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j]); } } } // Return the maximum value that can be obtained return dp[N][W];}int main(){ // Example usage int N = 3; int W = 4; vector<int> values = { 1, 2, 3 }; vector<int> weights = { 4, 5, 1 }; // Calling the knapsack function and printing the result int result = knapsack(N, W, values, weights); cout << result << endl; return 0;}// This code is contributed by Susobhan Akhuli |
Java
// Java code of the above approachimport java.util.*;public class Knapsack { // Function to solve the knapsack problem static int knapsack(int N, int W, List<Integer> values, List<Integer> weights) { // Initializing a 2D array for dynamic programming int[][] dp = new int[N + 1][W + 1]; // Loop through the items for (int i = 1; i < N + 1; i++) { // Loop through the weight capacity for (int j = 1; j < W + 1; j++) { // Check if the current item's weight // exceeds the capacity if (weights.get(i - 1) > j) { // If the weight is greater, take the // value without this item dp[i][j] = dp[i - 1][j]; } else { // If the weight is feasible, find the // maximum value considering whether to // take this item dp[i][j] = Math.max( values.get(i - 1) + dp[i - 1] [j - weights.get(i - 1)], dp[i - 1][j]); } } } // Return the maximum value that can be obtained return dp[N][W]; } public static void main(String[] args) { // Example usage int N = 3; int W = 4; List<Integer> values = new ArrayList<>(Arrays.asList(1, 2, 3)); List<Integer> weights = new ArrayList<>(Arrays.asList(4, 5, 1)); // Calling the knapsack function and printing the // result int result = knapsack(N, W, values, weights); System.out.println(result); }}// This code is contributed by Susobhan Akhuli |
Python3
def knapsack(N, W, values, weights): dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)] for i in range(1, N + 1): for j in range(1, W + 1): if weights[i-1] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(values[i-1] + dp[i-1] [j-weights[i-1]], dp[i-1][j]) return dp[N][W]# Example usageN = 3W = 4values = [1, 2, 3]weights = [4, 5, 1]result = knapsack(N, W, values, weights)print(result) |
Output
3
Time Complexity: O(N * W) where N is items and W is capacities.
Auxiliary Space: O(N * W) where N is items and W is capacities.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
