Problem 2 [50 points] Consider the following more general version of the Knapsac

Question

Problem 2 [50 points] Consider the following more general version of the Knapsack problem. There are p groups of objects 01, , Op and a knapsack capacity W. Each object r has a weight wr and a value Vx. Our goal is to select a subset of objects such that: the total weights of selected objects is at most W at most one objeet is selected from any group, and the total value of the selected objects is maximized. Suppose that n is the total number of objects in all the groups and V is the maximum value of , max . v1. Give an O(nW) time algorithm for this general Knapsack is an object any object, i.e., V- problem. Explain why your algorithm is correct and analyze the running time of your algorithm. Hint: Do a dynamic programming with increasing Knapsack capacity.

Explanation / Answer

Here is my implementation in C++. The function selectObjects() returns the total achievable weight else returns 0. It runs in O(n * maxWeight) where n = total number of objects and maxWeight = Knapsack Quantity. The complexity essentially the same as the classic algorithm that solves the original knapsack problem. We have used dynamic programming to solve this Knapsack problem as we have 1) Optimal Substructure(To include at most one item from each group) and 2) Overlapping Subproblems(To solve the problem recursively).

#include<iostream>

#include <algorithm>

#define max(a,b) (a > b ? a : b)

using namespace std;

int selectObjects(vector<vector<int>>& weight,

vector<vector<int>>& value,

int maxWeight) {

vector<int> last(maxWeight + 1, -1);

if (weight.empty()) {

return 0;

}

for (int i = 0; i < weight[0].size(); ++i) {

if (weight[0][i] > maxWeight) {

continue;

}

last[weight[0][i]] = max(last[weight[0][i]], value[0][i]);

}

vector<int> current(maxWeight + 1);

for (int i = 1; i < weight.size(); ++i) {

fill(current.begin(), current.end(), -1);

for (int j = 0; j < weight[i].size(); ++j) {

for (int k = weight[i][j]; k <= maxWeight; ++k) {

if (last[k - weight[i][j]] < 0) {

continue;

}

current[k] = max(current[k], last[k - weight[i][j]] + value[i][j]);

}

}

swap(current, last);

}

return *max_element(last.begin(), last.end());

}

int main() {

int p;

cout << "Number of groups: ";

cin >> p;

int n;

cout << "Number of objects in all groups: "

cin >> n;

vector<vector<int>> weight(p, n);

vector<vector<int>> value(p, n);

int W;

cout << "Enter KnapSack Capacity: ";

cin >> W;

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

cout << "Enter object values and weights for group " << p;

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

cin >> weight[i][j];

cin >> value[i][j];

}

}

auto result = selectObjects(W, weight, value, p, n);

cout << *result;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.