In the programming world, the knapsack problem is termed one of the very important questions. It includes selecting items with maximum value while considering weight constraints. In this article, we will learn about the knapsack and look at the duplicate item knapsack problem.

What is Knapsack Problem?

The knapsack problem is an optimization problem used in maths and computer science. The name ‘knapsack’ derives from a fictitious situation in which we must select a combination of products to maximize the overall value while remaining within the weight restriction of a rucksack with a limited carrying capacity.

The knapsack problem assumes that each item can only be chosen once, called as 0/1 knapsack problem. On the other hand, in some circumstances where duplicates are permitted, it leads to the unbounded knapsack problem or the knapsack problem with duplicate items.

Let’s first try to understand the knapsack problem using an example:

Let's say we have a knapsack with a limit weight of 5 units. Four items are provided to us, i.e., i1 of value $ 3 and weight 2 units, i2 of value $ 4 and weight 3 unit, i3 of value $ 5 and weight 4 unit, and i4 of value $ 6 and weight 5 units. The objective is to identify the set of items that maximizes the overall worthwhile staying within the weight limit of the knapsack.

After solving this question, we get that if we put i1 and i2 in the knapsack, then the overall value is maximum, which is equal to 7.

The knapsack problem has multiple forms, which mainly differ in their constraints:

0/1 Knapsack Problem
Fractional Knapsack Problem
Unbounded Knapsack Problem
Bounded Knapsack Problem

Let’s explore the Knapsack with Duplicate Items or Unbounded Knapsack Problem.

Understanding the Knapsack with Duplicate Items problem

The duplicate item knapsack problem involves a set of items, each of which has a value and a weight. The objective is to maximize the combined worth of the chosen products while ensuring that the combined weight does not surpass the knapsack's carrying capacity. Duplicate items can be selected more than once, making it more difficult to identify the best answer than in the classic knapsack problem.

Let's see an example to clearly understand this problem:

Suppose we have a knapsack with a limit weight of 50 units. Two items are provided to us, i.e., i1 of the value of $ 1 and weight of 1 unit and i2 of the value of $ 15 and weight of 25 units. The objective is to identify the set of items that maximizes the overall value while staying within the weight limit of the knapsack. We can use duplicate items.

Here, we have different ways to achieve this knapsack. They are:

2 quantities of 25 units weight item, i.e., two i2 items.
50 quantities of 1 unit weight item, i.e., fifty i1 items.
25 quantities of 1 unit weight item and 1 quantity of 25-unit weight items, i.e., twenty-five i1 items and one i2 item.

But to get the maximum overall value of the knapsack, we must choose the 2nd option, as its value is equal to $ 50. Whereas in 1^st case, the value is $ 30, and in 3^rdcase, the value is $ 40. So, in the knapsack, we have fifty i1 items.

Different approaches are present to solve this question. They are:

Recursive Approach
Memoization Method
Dynamic Programming

Let’s discuss each approach to solve the problem of Knapsack with duplicate items.

Recursive Approach

In the recursive approach, first form all the subsets of the items. Then, calculate the total weight and value of all subsets of items. Find all the subsets whose total weight is less than the knapsack weight. At last, choose the subset with the highest value among the subsets.

Let’s see the code for this approach in C++:

Example:

#include <iostream>

#include <climits>

using namespace std;

int find_max(int W, int wt[], int val[], int idx)

{

if (idx == 0) {

return (W / wt[0]) * val[0];

}

int notTake = 0 + find_max(W, wt, val, idx - 1);

int take = INT_MIN;

if (wt[idx] <= W) {

take = val[idx] + find_max(W - wt[idx], wt, val, idx);

}

return max(take, notTake);

}

int main()

{

int w = 50;

int val[] = { 1, 15 };

int wt[] = {1, 25};

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

cout << find_max(w, wt, val, n - 1);

return 0;

}

The output of this code is:

Output:

In this code, we use the recursive approach to solve the Knapsack with duplicate items problem by iteratively choosing the best option at each stage while taking into account the greatest value that can be reached by taking or leaving out each item.

Memoization Method

Another method to solve this question is using memoization. It helps to reduce the memory size to find the solution to this problem. Recalculating the same subproblems can be avoided by building a temporary array K[][] from the bottom up.

Let’s see its implementation in C++.

Example 2:

#include <iostream>

#include <climits>

#include <unordered_map>

using namespace std;

// Memoization table to store results of subproblems

unordered_map<int, int> memo;

int find_max(int W, int wt[], int val[], int idx)

{

    if (idx == 0)

    {

        return (W / wt[0]) * val[0];

    }

    // Check if the result for the current subproblem is already memoized

    if (memo.find(idx) != memo.end())

    {

        return memo[idx];

    }

    int notTake = 0 + find_max(W, wt, val, idx - 1);

    int take = INT_MIN;

    if (wt[idx] <= W)

    {

        take = val[idx] + find_max(W - wt[idx], wt, val, idx);

    }

    // Memoize the result of the current subproblem

    memo[idx] = max(take, notTake);

    return memo[idx];

}

int main()

{

    int w = 50;

    int val[] = {1, 15};

    int wt[] = {1, 25};

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

    cout << find_max(w, wt, val, n - 1) << endl;

    return 0;

}

The output of this code is:

Output:

In this code, to store the outcomes of subproblems, we added an unordered_map named memo. The indices of the items are represented by the keys in the memo table, and the corresponding values are the highest values that could be found for those indices.

Dynamic Programming

Dynamic programming is a method of problem-solving that divides difficult issues into overlapping subproblems and addresses each subproblem only once. To avoid repeating computations, it keeps the answers to the subproblems in a table or memoization array. By minimizing unnecessary calculations and increasing efficiency, it reduces the complexity of the problem and the amount of time required to solve it. Dynamic programming can be used to effectively address complicated issues, offering the best answers to a variety of computational difficulties.

The knapsack problem with duplicate items can be solved using dynamic programming by building a table and repeatedly determining the maximum value for each item and the weight limit. We can choose the best course of action by deciding whether to include or exclude each item in each capacity. The last value in the table's bottom-right corner is the highest possible value.

We can use the formula below to recursively calculate dp[].

dp[i] = 0

dp[i] = max(dp[i], dp[i-wt[j]] + val[j]

                   where j varies from 0

                   to n-1 such that:

wt[j] <= i

result = d[W]

Let’s see the code to solve Knapsack with duplicate items using dynamic programming.

Example 3:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int knapsack(int W, vector<int>& wt, vector<int>& val) {

    int n = wt.size();

    vector<int> dp(W + 1, 0); // Initialize a 1D dynamic programming array

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

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

            if (wt[j] <= i) {

                dp[i] = max(dp[i], dp[i - wt[j]] + val[j]);

            }

        }

    }

    return dp[W];

}

int main() {

    int w = 50;

    vector<int> val = {1, 15};

    vector<int> wt = {1, 25};

    int maxVal = knapsack(w, wt, val);

    cout << "Maximum value: " << maxVal << endl;

    return 0;

}

The output of this code is:

Output:

Maximum value: 50

This is the way to use dynamic programming to solve the question of Knapsack with duplicate items. We may effectively resolve this issue by decomposing it into smaller subproblems and computing the maximum value iteratively using a dynamic programming approach. The algorithm can be changed to accommodate the problem's requirements for complete copies of objects versus fractional knapsacks. We can successfully handle real-world situations involving duplicate goods by utilizing this algorithmic strategy, and we can also maximize the value of our choices within knapsack weight restrictions.

Conclusion

In this article, we have learnt the knapsack problem with duplicate items and solve it using different methods. We know about the knapsack problem. The knapsack problem with duplicate items is one of the important types of the classical knapsack problem. The ability to select an item more than once necessitates that we change how we go about finding the best answer.

← Prev Next →