# | Likes | Tech tags | Title | Creator | Created date |
---|---|---|---|---|---|
1 | 0 |
2022-11-06 00:17
|
|||
2 | 0 |
2022-11-08 02:55
|
A readable and commented \(O(Wn)\) dynamic programming solution for the knapsack problem, where \(W\) is the capacity of the knapsack and \(n\) is the number of items. Finds a solution for each subproblem of some non-greater capacity and some first-\(x\) set of items. Has memory complexity of \(O(Wn)\), which can be reduced to \(O(W)\) by keeping a DP array only for the last level, at the cost of making it harder to find the optimal set of items.
Caveat: Requires weights to be integers. Since weights and capacities are potentially exponential in input size, it's not a polynomial time solution in general case
#include<vector>
#include<algorithm>
struct KnapsackSolver {
struct Item {
int weight;
int value;
};
std::vector<Item> items_;
void add_item(int weight, int value) {
items_.push_back({weight, value});
}
int solve_knapsack_problem(int capacity) {
// Initializes the 2D array containing solutions to the subproblems
// sub_problem[x][c] = greatest attainable value for knapsack capacity c when using first x items
std::vector<std::vector<int> > sub_problem(items_.size() + 1, std::vector<int>(capacity+1, 0));
for(int x=1; x <= (int)items_.size(); x++) {
Item item = items_[x-1];
for(int c=0; c <= capacity; c++) {
// Apply the relation formula. Fundamentally, we either use item x or we don't, and then we can use
// the solution for the smaller sub-problem
sub_problem[x][c] = sub_problem[x-1][c];
if(c >= item.weight) {
sub_problem[x][c] = std::max(sub_problem[x][c], sub_problem[x-1][c-item.weight] + item.value);
}
}
}
return sub_problem[items_.size()][capacity]; // Return 'sub-problem' corresponding to the full problem
}
};
int main() {
KnapsackSolver solver;
solver.add_item(5, 7);
solver.add_item(4, 4);
solver.add_item(2, 4);
int result = solver.solve_knapsack_problem(6);
}
Dynamic Programming: Knapsack Problem - courses.cs.ut.ee
Knapsack problem: solving: 0-1 knapsack problem - wikipedia.org
Dynamic programming - wikipedia.org
classes | ||
std::vector |
en.cppreference.com | cplusplus.com |
functions | ||
std::vector::operator[] |
en.cppreference.com | cplusplus.com |
std::vector::push_back |
en.cppreference.com | cplusplus.com |
std::vector::vector |
en.cppreference.com | cplusplus.com |
Implement a solution for the Knapsack problem, that is, given a set of items with weights and values, find the maximum total value you can put into a knapsack of some limited capacity. Your solution should optimize for algorithmic complexity or speed. Create some instance of this problem with some set of items and output the maximum attainable total value for some capacity.