Teleporter: [Previous] | | | [Next]
Table of content
This blog isnt the best but worth spending time to read it
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
I. STATEMENT
Taking about the problem
Problem: During midnight, a thief breaks into a jewelry shop. There are $$$N$$$ priceful items whose value and weight are known. The item $$$p$$$ can be sold for $$$V_p$$$ money but having $$$C_p$$$ weight. There is a bag with infinity amount of space, means that any item can be pinto it while the item's value in the bag remain unchanged ! But, it can only hold maximumly $$$W$$$ weight.
Question: What is the value $$$V$$$ that the thief can steal from the shop.
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
II. EXAMPLE
To understand the problem better
3 8
2 10
4 20
6 30
40
There are 8 possible cases
{} -> 0 value, 0 weight
{1} -> 10 value, 2 weight
{2} -> 20 value, 4 weight
{3} -> 30 value, 6 weight
{1, 2} -> 30 value, 6 weight
{1, 3} -> 40 value, 8 weight - optimal
{2, 3} -> 50 value, 10 weight - invalid weight
{1, 2, 3} -> 60 value, 12 weight - invalid weight
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
III. Solution for small number of element — N
How much will you get in each possible subset ?
A. Permutation Approach (Bad) — $$$O(n!)$$$ time — $$$O(n)$$$ space
For each possible permutation, pick elements until it weight too much
The result is the maximum value sum, for which weight sum is not greater than $$$W$$$
Permutation Approach - O(n!) time - O(n) space#include <algorithm>
#include <iostream>
#include <cstring>
#include <numeric>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n], v[n];
for (int i = 0; i < n; ++i)
cin >> c[i] >> v[i];
int p[n];
iota(p, p + n, 0);
ll res = 0;
do {
ll sum_weight = 0;
ll sum_value = 0;
for (int i = 0; i < n; ++i)
{
int weight = c[p[i]];
int value = v[p[i]];
sum_weight += weight;
sum_value += value;
if (sum_weight > w)
{
break;
}
else
{
maximize(res, sum_value);
}
}
}
while (next_permutation(p, p + n));
cout << res;
return 0;
}
B. Bitmasking Approach (Good) — $$$O(2^n \times n)$$$ time — $$$O(n)$$$ space
Because the order isnt important, we just need to test all every possible subset
The result is the maximum value sum, for which weight sum is not greater than $$$W$$$
Bitmasking Approach - O(2^n * n) time - O(n) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n], v[n];
for (int i = 0; i < n; ++i)
cin >> c[i] >> v[i];
ll res = 0;
int lim = 1 << n;
for (int mask = 0; mask < lim; ++mask)
{
int weight = 0;
ll value = 0;
for (int i = 0; i < n; ++i)
{
if (mask >> i & 1)
{
weight += c[i];
value += v[i];
if (weight > w) break;
}
}
if (weight <= w)
{
maximize(res, value);
}
}
cout << res << endl;
return 0;
}
C. Meet-in-the-middle Approach (Better) — $$$O(2^{^{\frac{n}{2}}} \times \frac{n}{2})$$$ time — $$$O(2^{^{\frac{n}{2}}})$$$ space
Split the array into two halves $$$L$$$ and $$$R$$$. In each half, we will calculate every possible subsets. And in each subset we store a pair of $$$(value\ sum, weight\ sum)$$$
For each element $$$X(value_X, weight_X) \in L$$$, we need to find suitable element $$$Y(value_Y, weight_Y) \in R$$$ that satisfying maximum $$$value_R$$$ and $$$weight_L + weight_R \leq W$$$
Therefore, we can sort all the $$$R$$$ set by increasing weight. Let $$$maxval_Y = max(value_E | E \in R, weight_E \leq weight_Y)$$$. Then for each $$$X \in L$$$, we can find its suitable $$$Y$$$ by binary search in $$$O(log\ |R|)$$$ with $$$O(|R|)$$$ precalculation
Meet in the middle approach - O(2^(n/2) * (n/2)) time - O(2^(n/2)) space#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
#define all(x) (x).begin(), (x).end()
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
struct Node
{
ll maxval = 0;
ll value;
int weight;
Node (ll value = 0, int weight = 0)
: value(value), weight(weight) {}
};
int n, w;
void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
int n = c.size(); /// Important !!!
int lim = 1 << n;
for (int mask = 0; mask < lim; ++mask)
{
ll weight = 0;
ll value = 0;
for (int i = 0; i < n; ++i)
{
if (mask >> i & 1)
{
weight += c[i];
value += v[i];
if (weight > w) break;
}
}
if (weight <= w)
{
S.push_back(Node(value, weight));
}
}
}
int main()
{
cin >> n >> w;
int c[n], v[n];
for (int i = 0; i < n; ++i)
cin >> c[i] >> v[i];
int m = n / 2;
vector<int> cl, cr;
vector<int> vl, vr;
for (int i = 0; i < n; ++i)
{
if (i < m)
{
cl.push_back(c[i]);
vl.push_back(v[i]);
}
else
{
cr.push_back(c[i]);
vr.push_back(v[i]);
}
}
vector<Node> Sl, Sr;
solve(cl, vl, Sl);
solve(cr, vr, Sr);
sort(all(Sr), [](const Node &a, const Node &b) {
return (a.weight != b.weight) ? a.weight < b.weight : a.value < b.value;
});
ll maxval = 0;
for (Node &x : Sr)
{
maximize(maxval, x.value);
x.maxval = maxval;
}
ll res = 0;
for (Node &y : Sl)
{
for (int l = 0, r = int(Sr.size()) - 1; l <= r; )
{
int m = (l + r) >> 1;
Node x = Sr[m];
if (x.weight + y.weight <= w)
{
maximize(res, x.maxval + y.value);
l = m + 1;
}
else
{
r = m - 1;
}
}
}
cout << res;
return 0;
}
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
IV. Solution for small sum of weight — C[i]
What is the maximum value possible when your bag is exact $$$W$$$ weight ?
A) Recursive Dynamic Programming — $$$O(N \times W)$$$ time — $$$O(N \times W)$$$ space
Recursive Approach - O(NW) time - O(NW) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXW = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
if (s > w) return -LINF; /// Using too much weight
if (i > n) return 0; /// No available item to add into the bag
ll &res = f[i][s];
if (res != -1) return res;
maximize(res, magic(i + 1, s + 0) + 0); /// Not using this item
maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item
return res;
}
int main()
{
cin >> n >> w;
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
memset(f, -1, sizeof(f));
cout << magic();
return 0;
}
B) Iterative Dynamic Programming — $$$O(N \times W)$$$ time — $$$O(N \times W)$$$ space
Bad Approach - O(N^2 * W^2) time#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n + 1], v[n + 1];
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
ll res = 0;
ll f[n + 1][w + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i)
{
for (int s = 1; s <= w; ++s)
{
for (int j = 1; j < i; ++j)
{
for (int t = 0; t <= s; ++t)
{
maximize(f[i][s], f[i][t] + 0);
}
for (int t = 0; t + c[i] <= s; ++t)
{
maximize(f[i][s], f[i - 1][t] + v[i]);
}
}
maximize(res, f[i][s]);
}
}
cout << res;
return 0;
}
Iterative Approach - O(NW) time - O(NW) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n + 1], v[n + 1];
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
ll f[n + 1][w + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i)
{
for (int s = 1; s <= w; ++s)
{
f[i][s] = f[i - 1][s];
if (s >= c[i])
{
maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);
}
}
}
ll res = 0;
for (int s = 0; s <= w; ++s)
maximize(res, f[n][s]);
cout << res;
return 0;
}
Prefixmax DP Approach - O(NW) time - O(NW) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n + 1], v[n + 1];
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
ll f[n + 1][w + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i)
{
for (int s = 1; s <= w; ++s)
{
f[i][s] = max(f[i][s - 1], f[i - 1][s]);
if (s >= c[i])
{
maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);
}
}
}
cout << f[n][w];
return 0;
}
C) Recursive Dynamic Programming (Space optimization) — $$$O(N \times W)$$$ time — $$$O(N + W)$$$ space
A) O(2W) DP space
Observe: $$$\forall i > 0, f[i][x]$$$ depends on $$$f[i - 1]$$$ and $$$f[i]$$$ only, hence we just need 2 dp array space
Define: When we calculate at pth element, we have $$$\underset{x \equiv p (mod 2)}{f[x]}$$$ is current dp array, $$$\underset{y \equiv p + 1 (mod 2)}{f[y]}$$$ is previous dp array
Transistion: $$$f[i][s] = max(f[i - 1][s], f[i - 1][s - c_i] + v_i)$$$ equivalent to $$$f[x][s] = max(f[y][s], f[y][s - c_i] + v_i)$$$
Space Optimization Approach - O(NW) time - O(N + 2W) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n + 1], v[n + 1];
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
ll f[2][w + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])
{
bool cur = i & 1;
bool pre = !cur;
for (int s = 1; s <= w; ++s)
{
f[cur][s] = f[pre][s];
if (s >= c[i])
{
maximize(f[cur][s], f[pre][s - c[i]] + v[i]);
}
}
}
ll res = 0;
for (int s = 0; s <= w; ++s)
maximize(res, f[n & 1][s]);
cout << res;
return 0;
}
B) O(W) 1D — DP space
- From the above algorithm, we can change the inner loop
Inner Part ll f[2][w + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])
{
bool cur = i & 1;
bool pre = !cur;
for (int s = 1; s <= w; ++s)
f[cur][s] = f[pre][s];
for (int s = w; s >= c[i]; --s)
maximize(f[cur][s], f[pre][s - c[i]] + v[i]);
}
- Kinda tricky, but we only need one array, for each query $$$f[s]$$$ stand for maximum value with bag of weight $$$s$$$ upto that query.
Inner Part ll f[w + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])
{
bool cur = i & 1;
bool pre = !cur;
for (int s = 1; s <= w; ++s) /// Unneeded loop
f[s] = f[s];
for (int s = w; s >= c[i]; --s)
maximize(f[s], f[s - c[i]] + v[i]);
}
- Notice that it is required for the second-inner-loop to iterate from $$$w$$$ downto $$$c_i$$$. Here is the reason
From c[i] upto w for which
f[cur][s] = f[s] that updated
f[pre][s] = f[s] that not update yet
the part
for (int s = c; s <= w; ++s)
maximize(f[s], f[s - c] + v);
equivalent to
for (int s = c; s <= w; ++s)
maximize(f[cur][s], f[cur][s - c] + v);
From w downto c[i] for which
f[cur][s] = f[s] that updated
f[pre][s] = f[s] that not update yet
the part
for (int s = w; s >= c; --s)
maximize(f[s], f[s - c] + v);
equivalent
for (int s = w; s >= c; --s)
maximize(f[cur][s], f[pre][s - c] + v);
- Finally, here is 1D Dynamic Programming Solution
Space Optimization Approach - O(NW) time - O(N + 1W) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n + 1], v[n + 1];
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
ll f[w + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i)
for (int s = w; s >= c[i]; --s)
maximize(f[s], f[s - c[i]] + v[i]);
cout << f[w];
return 0;
}
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
V. Solution for small sum of value — V[i]
What is the minimum bag weight possible when it is exact $$$S$$$ sum value ?
A) Recursive Dynamic Programming — $$$O(N \times SUM)$$$ time — $$$O(N \times SUM)$$$ space
Recursive Approach - O(NSUM) time - O(NSUM) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXSUM = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXSUM];
ll magic(int i = 1, int s = 0)
{
if (s < 0) return +LINF;
if (i > n) return (s == 0) ? 0 : +LINF;
ll &res = f[i][s];
if (res != -1) return res;
res = +LINF;
minimize(res, magic(i + 1, s - 0) + 0);
minimize(res, magic(i + 1, s - v[i]) + c[i]);
return res;
}
int main()
{
cin >> n >> w;
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
int sum = 0;
for (int i = 1; i <= n; ++i)
sum += v[i];
memset(f, -1, sizeof(f));
for (int res = sum; res >= 0; --res)
{
if (magic(1, res) <= w)
{
cout << res;
return 0;
}
}
return 0;
}
B) Iterative Dynamic Programming — $$$O(N \times SUM)$$$ time — $$$O(N \times SUM)$$$ space
Iterative Approach - O(NSUM) time - O(NSUM) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n + 1], v[n + 1];
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
int sum = 0;
for (int i = 1; i <= n; ++i)
sum += v[i];
ll f[n + 1][sum + 1];
memset(f, +LINF, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; ++i)
{
for (int s = 0; s <= sum; ++s)
{
f[i][s] = f[i - 1][s];
if (s >= v[i])
{
minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);
}
}
}
for (int res = sum; res >= 0; --res)
{
if (f[n][res] <= w)
{
cout << res;
return 0;
}
}
return 0;
}
C) Iterative Dynamic Programming (Space Optimization) — $$$O(N \times SUM)$$$ time — $$$O(N + SUM)$$$ space
A) O(2SUM) DP space
Observe: $$$\forall i > 0, f[i][x]$$$ depends on $$$f[i - 1]$$$ and $$$f[i]$$$ only, hence we just need 2 dp array space
Define: When we calculate at pth element, we have $$$\underset{x \equiv p (mod 2)}{f[x]}$$$ is current dp array, $$$\underset{y \equiv p + 1 (mod 2)}{f[y]}$$$ is previous dp array
Transistion: $$$f[i][s] = min(f[i - 1][s], f[i - 1][s - v_i] + c_i)$$$ equivalent to $$$f[x][s] = min(f[y][s], f[y][s - v_i] + c_i)$$$
Space Optimization Approach - O(NSUM) time - O(N + 2SUM) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n + 1], v[n + 1];
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
int sum = 0;
for (int i = 1; i <= n; ++i)
sum += v[i];
ll f[2][sum + 1];
memset(f, +LINF, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; ++i)
{
bool cur = i & 1;
bool pre = !cur;
for (int s = 0; s <= sum; ++s)
{
f[cur][s] = f[pre][s];
if (s >= v[i])
{
minimize(f[cur][s], f[pre][s - v[i]] + c[i]);
}
}
}
for (int res = sum; res >= 0; --res)
{
if (f[n & 1][res] <= w)
{
cout << res;
return 0;
}
}
return 0;
}
B) O(SUM) 1D — DP space
- From the above algorithm, we can change the inner loop
Inner Part ll f[2][sum + 1];
memset(f, +LINF, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; ++i)
{
bool cur = i & 1;
bool pre = !cur;
for (int s = 0; s <= sum; ++s)
{
f[cur][s] = f[pre][s];
if (s >= v[i])
{
minimize(f[cur][s], f[pre][s - v[i]] + c[i]);
}
}
}
- Kinda tricky, but we only need one array, for each query $$$f[s]$$$ stand for maximum value with bag of weight $$$s$$$ upto that query.
Inner Part ll f[2][sum + 1];
memset(f, +LINF, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; ++i)
{
bool cur = i & 1;
bool pre = !cur;
for (int s = 0; s <= w; ++s) /// Unneeded loop
f[s] = f[s];
for (int s = sum; s >= v[i]; --s)
minimize(f[s], f[s - v[i]] + c[i]);
}
- Notice that it is required for the second-inner-loop to iterate from $$$sum$$$ downto $$$v_i$$$. Here is the reason
From v[i] upto sum for which
f[cur][s] = f[s] that updated
f[pre][s] = f[s] that not update yet
the part
for (int s = v[i]; s <= sum; ++s)
minimize(f[s], f[s - v[i]] + c[i]);
equivalent to
for (int s = v[i]; s <= sum; ++s)
minimize(f[cur][s], f[cur][s - v[i]] + c[i]);
From sum downto v[i] for which
f[cur][s] = f[s] that updated
f[pre][s] = f[s] that not update yet
the part
for (int s = sum; s >= v[i] --s)
minimize(f[s], f[s - v[i]] + c[i]);
equivalent to
for (int s = sum; s >= v[i] --s)
minimize(f[cur][s], f[pre][s - v[i]] + c[i]);
- Finally, here is 1D Dynamic Programming Solution
Space Optimization Approach - O(NSUM) time - O(N + SUM) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n + 1], v[n + 1];
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
int sum = 0;
for (int i = 1; i <= n; ++i)
sum += v[i];
ll f[sum + 1];
memset(f, +LINF, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; ++i)
for (int s = sum; s >= v[i]; --s)
minimize(f[s], f[s - v[i]] + c[i]);
for (int res = sum; res >= 0; --res)
{
if (f[res] <= w)
{
cout << res;
return 0;
}
}
return 0;
}
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
VII. Tracing for selected elements
Which next state will lead to the best result ?
A) Solution for small number of element — N
- A) Permutation Approach: We will update selected elements when we see a better solution
Permutation - O(n!) time - O(n) space#include <algorithm>
#include <iostream>
#include <cstring>
#include <numeric>
#include <vector>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n], v[n];
for (int i = 0; i < n; ++i)
cin >> c[i] >> v[i];
int p[n];
iota(p, p + n, 0);
vector<int> selected;
ll res = 0;
do {
bool better = false;
vector<int> current;
ll sum_weight = 0;
ll sum_value = 0;
for (int i = 0; i < n; ++i)
{
int weight = c[p[i]];
int value = v[p[i]];
sum_weight += weight;
sum_value += value;
if (sum_weight > w)
{
break;
}
else
{
current.push_back(p[i]);
if (res < sum_value)
{
better = true;
res = sum_value;
}
}
}
if (better) selected = current;
}
while (next_permutation(p, p + n));
cout << res << '\n';
sort(selected.begin(), selected.end());
for (int p : selected)
{
cout << p + 1 << ' ' << c[p] << ' ' << v[p] << '\n';
}
return 0;
}
- B) Bitmasking Approach: We will update bitmask when we see a better solution
O(2^n) time - O(n) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n], v[n];
for (int i = 0; i < n; ++i)
cin >> c[i] >> v[i];
ll res = 0;
int selected = 0;
int lim = 1 << n;
for (int mask = 0; mask < lim; ++mask)
{
ll weight = 0;
ll value = 0;
for (int i = 0; i < n; ++i)
{
if (mask >> i & 1)
{
weight += c[i];
value += v[i];
if (weight > w) break;
}
}
if (weight <= w)
{
if (res <= value)
{
res = value;
selected = mask;
}
}
}
cout << res << '\n';
for (int i = 0; i < n; ++i)
{
if (selected >> i & 1)
{
cout << i + 1 << ' ' << c[i] << ' ' << v[i] << '\n';
}
}
return 0;
}
- C) Meet-in-the-middle Approach: We will update bitmask when we see a better solution AND ON DP-CALCULATION.
Bitmasking - O(2^(n/2) * (n/2)) time - O(2^(n/2)) space#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
#define all(x) (x).begin(), (x).end()
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
struct Node
{
ll maxval = 0;
int maxmask = 0;
int mask;
ll value;
int weight;
Node (int mask = 0, ll value = 0, int weight = 0)
: mask(mask), value(value), weight(weight) {}
};
int n, w;
void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
int n = c.size(); /// Important !!!
int lim = 1 << n;
for (int mask = 0; mask < lim; ++mask)
{
ll weight = 0;
ll value = 0;
for (int i = 0; i < n; ++i)
{
if (mask >> i & 1)
{
weight += c[i];
value += v[i];
if (weight > w) break;
}
}
S.push_back(Node(mask, value, weight));
}
}
int main()
{
cin >> n >> w;
int c[n], v[n];
for (int i = 0; i < n; ++i)
cin >> c[i] >> v[i];
int m = n / 2;
vector<int> cl, vl;
for (int i = 0; i < m; ++i)
{
cl.push_back(c[i]);
vl.push_back(v[i]);
}
vector<int> cr, vr;
for (int i = m; i < n; ++i)
{
cr.push_back(c[i]);
vr.push_back(v[i]);
}
vector<Node> Sl, Sr;
solve(cl, vl, Sl);
solve(cr, vr, Sr);
sort(all(Sr), [](const Node &a, const Node &b) {
return (a.weight != b.weight) ? a.weight < b.weight : a.value > b.value;
});
ll maxval = 0;
int maxmask = 0;
for (Node &x : Sr)
{
if (maxval < x.value)
{
maxval = x.value;
maxmask = x.mask;
}
x.maxval = maxval;
x.maxmask = maxmask;
}
ll res = 0;
int mask_l = 0;
int mask_r = 0;
for (Node &y : Sl)
{
for (int l = 0, r = int(Sr.size()) - 1; l <= r; )
{
int m = (l + r) >> 1;
Node x = Sr[m];
if (x.weight + y.weight <= w)
{
if (res < x.maxval + y.value)
{
res = x.maxval + y.value;
mask_l = y.mask;
mask_r = x.maxmask;
}
l = m + 1;
}
else
{
r = m - 1;
}
}
}
vector<int> selected;
for (int i = 0; i < m; ++i)
if (mask_l >> i & 1)
selected.push_back(i);
for (int i = 0; i < n - m; ++i)
if (mask_r >> i & 1)
selected.push_back(i + m);
cout << res << '\n';
cout << selected.size() << '\n';
for (int p : selected)
{
cout << p + 1 << ' ' << c[p] << ' ' << v[p] << '\n';
}
return 0;
}
B) Solution for small sum of weight — C[i]
- A) Recursive Dynamic Programming: Starting from $$$(i = 0, s = 0)$$$, we already have $$$magic(i,s)$$$ return the best result, $$$magic(i + 1,s + 0) + 0)$$$ or/and $$$magic(i + 1, s + c[i]) + v[i]$$$ will be the best result
Trace cases $$$magic(i,s) = magic(i + 1,s + c[i]) + v[i])$$$ take this element will lead to the best result
$$$magic(i,s) = magic(i + 1,s + 0) + 0) \neq magic(i + 1, s + c[i])+ v[i]$$$ take this element wont lead to the best result
$$$magic(i,s) = magic(i + 1,s + 0) + 0) = magic(i + 1, s + c[i])+ v[i]$$$ either you take or not, you will find best result
When $$$magic(i, s) = magic(X, Y)$$$, trace to next state $$$(i = X, s = Y)$$$
When $$$magic(i, s) = magic(X, Y) = magic(P, Q)$$$, you can either trace to next state $$$(i = X, s = Y)$$$ or $$$(i = P, s = Q)$$$
Recursive DP - O(NW) time - O(NW) space#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXW = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
if (s > w) return -LINF; /// Using too much weight
if (i > n) return 0; /// No available item to add into the bag
ll &res = f[i][s];
if (res != -1) return res;
maximize(res, magic(i + 1, s + 0) + 0); /// Not using this item
maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item
return res;
}
vector<int> selected;
void trace(int i = 1, int s = 0)
{
if (s > w) return ;
if (i > n) return ;
ll res = magic(i, s);
if (res == magic(i + 1, s + 0) + 0)
{
return trace(i + 1, s + 0);
}
else
{
selected.push_back(i);
return trace(i + 1, s + c[i]);
}
}
int main()
{
cin >> n >> w;
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
memset(f, -1, sizeof(f));
cout << magic() << '\n';
trace();
cout << selected.size() << '\n';
for (int p : selected)
{
cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
}
return 0;
}
- B) Iterative Dynamic Programming:
Prefixmax Iterative DP - O(NW) time - O(NW) space#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n + 1], v[n + 1];
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
ll f[n + 1][w + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i)
{
for (int s = 1; s <= w; ++s)
{
f[i][s] = max(f[i][s - 1], f[i - 1][s]);
if (s >= c[i])
{
maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);
}
}
}
vector<int> selected;
for (int i = n, s = w; i >= 1 && s >= 1; )
{
if (f[i][s] == f[i - 1][s - c[i]] + v[i])
{
selected.push_back(i);
s -= c[i];
i -= 1;
continue;
}
if (f[i][s - 1] > f[i - 1][s])
{
--s;
}
else /// f[i][s] = f[i - 1][s]
{
--i;
}
}
cout << f[n][w] << '\n';
cout << selected.size() << '\n';
for (int p : selected)
{
cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
}
return 0;
}
- C) Iterative Dynamic Programming (Space Optimization):
Explanation The idea is based on Lusterdawn's explanation and jiangly's solution
Let $$$calc(*f, l, r)$$$ is the function that calculate the answer for items $$$l, l + 1, \dots, r$$$ with $$$*f$$$ the 1D memorization table
For convention, let $$$calc$$$ return the value of $$$min(w, \overset{r}{\underset{i = l}{\Sigma}} c_i)$$$ — maximal possible weight created
First we calculate $$$calc(*f, 1, n)$$$, after having the maximal value of the whole items, we can find the minimal weight that return such value. Or $$$weight_used = min(p | f[p] = res)$$$
Let $$$trace(s, l, r)$$$ is the function that tracing for all elements, whose sum weight equal $$$s$$$ and sum value is max
If $$$(l = r)$$$, we will consider to select this item or not. (This item is selected when $$$s = c_l$$$)
Split the items into two halves: $$$[l, m]$$$ and $$$(m, r]$$$ and then calculate DP: $$$sleft = calc(*L, l, m + 0)$$$ and $$$sright = calc(*R, m + 1, r)$$$
We find such $$$pleft$$$ and $$$pright$$$ satisfy $$$pleft + pright = s$$$ that returning $$$max(L[pleft] + R[pright])$$$. Then we trace from $$$trace(pleft, l, m + 0)$$$ to $$$trace(pright, m + 1, r)$$$ (ordered selected item)
Code#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
const int LIM_N = 111;
const int LIM_W = 1e6 + 16;
int n, w;
int c[LIM_N], v[LIM_N];
ll f[LIM_W];
int calc(ll *f, int l = 1, int r = n)
{
ll upper = 0;
for (int i = l; i <= r; ++i)
upper += c[i];
minimize(upper, (ll)w);
for (int s = 0; s <= upper; ++s)
f[s] = 0;
for (int i = l; i <= r; ++i)
for (int s = upper; s >= c[i]; --s)
maximize(f[s], f[s - c[i]] + v[i]);
return upper;
}
ll L[LIM_W], R[LIM_W];
vector<int> selected;
void trace(int s = w, int l = 1, int r = n)
{
if (l == r)
{
if (s == c[l])
{
selected.push_back(l);
}
return ;
}
int m = (l + r) >> 1;
int sleft = calc(L, l, m + 0);
int sright = calc(R, m + 1, r);
ll mx = -1;
int pleft = 0;
int pright = s;
for (int v = max(0, s - sright); v <= min(s, sleft); ++v)
{
if (mx < L[v] + R[s - v])
{
mx = L[v] + R[s - v];
pleft = v;
pright = s - v;
}
}
trace(pleft , l, m + 0);
trace(pright, m + 1, r);
}
int main()
{
cin >> n >> w;
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
calc(f);
ll res = f[w];
int weight_used = max_element(f, f + w + 1) - f;
trace(weight_used);
cout << res << '\n';
cout << selected.size() << '\n';
for (int p : selected)
{
cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
}
return 0;
}
C) Solution for small sum of value — V[i]
- A) Recursive Dynamic Programming: Starting from $$$(i = 0, s = res)$$$, we already have $$$magic(i,s)$$$ return the best result, $$$magic(i + 1,s + 0) + 0)$$$ or/and $$$magic(i + 1, s - v[i]) + c[i]$$$ will be the best result
Trace cases $$$magic(i,s) = magic(i + 1,s - v[i]) + c[i])$$$ take this element will lead to the best result
$$$magic(i,s) = magic(i + 1,s + 0) + 0) \neq magic(i + 1, s - v[i]) + c[i]$$$ take this element wont lead to the best result
$$$magic(i,s) = magic(i + 1,s + 0) + 0) = magic(i + 1, s - v[i]) + c[i]$$$ either you take or not, you will find best result
When $$$magic(i, s) = magic(X, Y)$$$, trace to next state $$$(i = X, s = Y)$$$
When $$$magic(i, s) = magic(X, Y) = magic(P, Q)$$$, you can either trace to next state $$$(i = X, s = Y)$$$ or $$$(i = P, s = Q)$$$
Recursive DP - O(NSUM) time - O(NSUM) space#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXSUM = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXSUM];
ll magic(int i = 1, int s = 0)
{
if (s < 0) return +LINF;
if (i > n) return (s == 0) ? 0 : +LINF;
ll &res = f[i][s];
if (res != -1) return res;
res = +LINF;
minimize(res, magic(i + 1, s - 0) + 0);
minimize(res, magic(i + 1, s - v[i]) + c[i]);
return res;
}
vector<int> selected;
void trace(int i = 1, int s = 0)
{
if (s < 0) return ;
if (i > n) return ;
ll res = magic(i, s);
if (res == magic(i + 1, s + 0) + 0)
{
return trace(i + 1, s + 0);
}
else
{
selected.push_back(i);
return trace(i + 1, s - v[i]);
}
}
int main()
{
cin >> n >> w;
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
int sum = 0;
for (int i = 1; i <= n; ++i)
sum += v[i];
memset(f, -1, sizeof(f));
for (int res = sum; res >= 0; --res)
{
if (magic(1, res) <= w)
{
trace(1, res);
cout << res << '\n';
cout << selected.size() << '\n';
for (int p : selected)
{
cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
}
return 0;
}
}
return 0;
}
- B) Iterative Dynamic Programming:
Iterative DP - O(NSUM) time - O(NSUM) space#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
int c[n + 1], v[n + 1];
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
int sum = 0;
for (int i = 1; i <= n; ++i)
sum += v[i];
ll f[n + 1][sum + 1];
memset(f, +LINF, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; ++i)
{
for (int s = 0; s <= sum; ++s)
{
f[i][s] = f[i - 1][s];
if (s >= v[i])
{
minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);
}
}
}
int res = sum;
while (f[n][res] > w) --res;
vector<int> selected;
for (int i = n, s = res; i >= 1 && s >= 1; )
{
if (f[i][s] == f[i - 1][s - v[i]] + c[i])
{
selected.push_back(i);
s -= v[i];
i -= 1;
}
else
{
--i;
}
}
cout << res << '\n';
cout << selected.size() << '\n';
for (int p : selected)
{
cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
}
return 0;
}
- C) Iterative Dynamic Programming (Space Optimization):
Explanation Let $$$calc(*f, l, r)$$$ is the function that calculate the answer for items $$$l, l + 1, \dots, r$$$ with $$$*f$$$ the 1D memorization table
For convention, let $$$calc$$$ return the value of $$$\overset{r}{\underset{i = l}{\Sigma}} v_i$$$ — maximal possible value created
First we calculate $$$calc(*f, 1, n)$$$, after having the minimal weight of the whole items, we can find the maximal value that return such weight. Or $$$res = max(p | f[p] \leq w)$$$
Let $$$trace(s, l, r)$$$ is the function that tracing for all elements, whose sum value equal $$$s$$$ and sum weight is min
If $$$(l = r)$$$, we will consider to select this item or not. (This item is selected when $$$s = v_l$$$)
Split the items into two halves: $$$[l, m]$$$ and $$$(m, r]$$$ and then calculate DP: $$$sleft = calc(*L, l, m + 0)$$$ and $$$sright = calc(*R, m + 1, r)$$$
We find such $$$pleft$$$ and $$$pright$$$ satisfy $$$pleft + pright = s$$$ that returning $$$min(L[pleft] + R[pright])$$$. Then we trace from $$$trace(pleft, l, m + 0)$$$ to $$$trace(pright, m + 1, r)$$$ (ordered selected item)
Code#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
const int LIM_N = 111;
const int LIM_S = 1e6 + 16;
int n, w;
int c[LIM_N], v[LIM_N];
ll f[LIM_S + 1];
int calc(ll *f, int l = 1, int r = n)
{
int upper = 0;
for (int i = l; i <= r; ++i)
upper += v[i];
f[0] = 0;
for (int s = upper; s >= 1; --s)
f[s] = +LINF;
for (int i = l; i <= r; ++i)
for (int s = upper; s >= v[i]; --s)
minimize(f[s], f[s - v[i]] + c[i]);
return upper;
}
vector<int> selected;
ll L[LIM_S + 1], R[LIM_S + 1];
void trace(int s = LIM_S, int l = 1, int r = n)
{
if (l == r)
{
if (s == v[l])
{
selected.push_back(l);
}
return ;
}
int m = (l + r) >> 1;
int sleft = calc(L, l, m + 0);
int sright = calc(R, m + 1, r);
int mn = +INF;
int pleft = 0;
int pright = s;
for (int v = max(0, s - sright); v <= min(s, sleft); ++v)
{
if (mn > L[v] + R[s - v])
{
mn = L[v] + R[s - v];
pleft = v;
pright = s - v;
}
}
trace(pleft , l, m + 0);
trace(pright, m + 1, r);
}
int main()
{
cin >> n >> w;
for (int i = 1; i <= n; ++i)
cin >> c[i] >> v[i];
int res = calc(f);
while (f[res] > w) --res;
trace(res);
int ans = 0;
for (int p : selected)
ans += v[p];
cout << ans;
// cout << res << '\n';
// cout << selected.size() << '\n';
// for (int p : selected)
// {
// cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
// }
return 0;
}
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
VII. Other solutions
How to solve the problem with special condition ?
A) Fractional Knapsack & Greedy Approach
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
VIII. Online Algorithm
How to solve the problem when you need to output the result whenever you receive a new item ?
A) Solution for small number of element — N
- A) Permutation Approach: Really not worth being used thought it is possible to optimize it
Explanation For the $$$ith$$$ query, input the $$$ith$$$ element and iterating all bitmasks with exactly $$$ith$$$ bits
Optimization (DP bitmask): Effective and reduce $$$O(n)$$$ calculating time with the exchange of $$$O(2^N)$$$ space
Bitmasking Approach - O(2^N * N) time - O(n) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
ll res = 0;
ll c[n], v[n];
for (int i = 1; i <= n; ++i)
{
cin >> c[i] >> v[i];
int L = 1 << i;
int R = 1 << (i + 1);
for (int mask = L; mask < R; ++mask)
{
ll weight = 0;
ll value = 0;
for (int j = 1; j <= i; ++j)
{
if (mask >> j & 1)
{
weight += c[j];
value += v[j];
if (weight > w) break;
}
}
if (weight <= w)
{
maximize(res, value);
}
}
cout << res << '\n';
}
return 0;
}
DP Bitmask Approach - O(2^N) time - O(2^N) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
const int LIM = 1 << 20;
ll dpc[LIM], dpv[LIM];
int main()
{
int n, w;
cin >> n >> w;
ll res = 0;
for (int i = 0; i < n; ++i)
{
ll c, v;
cin >> c >> v;
for (int mask = (1 << i); mask < (1 << (i + 1)); ++mask)
{
dpc[mask] = dpc[mask ^ (1 << i)] + c;
dpv[mask] = dpv[mask ^ (1 << i)] + v;
if (dpc[mask] <= w)
maximize(res, dpv[mask]);
}
cout << res << '\n';
}
return 0;
}
- C) Iterating Deque Approach:
Explanation Let assume each item in deque is one way to fill up the bag with exact $$$weight$$$ and $$$value$$$
For the $$$ith$$$ query, we will input the $$$ith$$$ item, then iterating for each element $$$e$$$ in deque to add to deque a new item that is the sum of $$$ith$$$ item and $$$e$$$ item
Branch and bound (Eliminate all item whose weight > w) — Effective in normal — Highly effective when randomly generating weight
Branch and bound (Minimizing weight / maximizing value) — Not recommended to use — The good thing is when one branch is used, it would eliminate $$$O(2^k)$$$ cases — The bad thing is it increases both theoretical and practical time and space complexity significantly
Deque approach with little optimization - O(min(W, 2^N)) time - O(2^N) space#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>
using namespace std;
void file(const string FILE = "Test")
{
freopen((FILE + ".INP").c_str(), "r", stdin);
freopen((FILE + ".OUT").c_str(), "w", stdout);
}
char __;
template<typename T>
void getUnsign(T &x)
{
while (__ = getchar(), __ < '0' || __ > '9');
x = (__ - '0');
while (__ = getchar(), __ >= '0' && __ <= '9')
x = (x << 3) + (x << 1) + (__ - '0');
}
template<typename T>
void getSigned(T &x)
{
while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
bool sign(__ == '-');
if (sign) __ = getchar();
x = (__ - '0');
while (__ = getchar(), __ >= '0' && __ <= '9')
x = (x << 3) + (x << 1) + (__ - '0');
if (sign) x = -x;
}
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;
const int LIM = 0;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
struct item
{
ll weight;
ll value;
item (ll weight = 0, ll value = 0)
: weight(weight), value(value) {}
void operator += (const item &other)
{
weight += other.weight;
value += other.value;
}
};
int main()
{
int n;
ll w;
cin >> n >> w;
ll res = 0;
deque<item> S;
S.push_back(item(0, 0));
for (int i = 1; i <= n; ++i)
{
ll c, v;
cin >> c >> v;
if (c > w) continue;
deque<item> T;
for (item e : S)
{
e += item(c, v);
if (e.weight <= w)
{
T.push_back(e);
maximize(res, e.value);
}
}
for (const item &e : T)
S.push_back(e);
cout << res << '\n';
}
return 0;
}
Deque approach with bad optimization - O(min(W, 2^N * N)) time - O(2^N * N) space
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>
#include <map>
using namespace std;
void file(const string FILE = "Test")
{
freopen((FILE + ".INP").c_str(), "r", stdin);
freopen((FILE + ".OUT").c_str(), "w", stdout);
}
char __;
template<typename T>
void getUnsign(T &x)
{
while (__ = getchar(), __ < '0' || __ > '9');
x = (__ - '0');
while (__ = getchar(), __ >= '0' && __ <= '9')
x = (x << 3) + (x << 1) + (__ - '0');
}
template<typename T>
void getSigned(T &x)
{
while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
bool sign(__ == '-');
if (sign) __ = getchar();
x = (__ - '0');
while (__ = getchar(), __ >= '0' && __ <= '9')
x = (x << 3) + (x << 1) + (__ - '0');
if (sign) x = -x;
}
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;
const int LIM = 0;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
struct item
{
ll weight;
ll value;
item (ll weight = 0, ll value = 0)
: weight(weight), value(value) {}
void operator += (const item &other)
{
weight += other.weight;
value += other.value;
}
};
map<ll, ll> minC;
map<ll, ll> maxV;
bool update(ll &c, ll &v)
{
bool ok = false;
if (minC.count(v) == false || minC[v] > c)
{
minC[v] = c;
ok = true;
}
if (maxV.count(c) == false || maxV[c] < v)
{
maxV[c] = v;
ok = true;
}
return ok;
}
int main()
{
int n;
ll w;
cin >> n >> w;
ll res = 0;
deque<item> S;
minC[0] = 0;
maxV[0] = 0;
S.push_back(item(0, 0));
for (int i = 1; i <= n; ++i)
{
ll c, v;
cin >> c >> v;
if (c > w) continue;
deque<item> T;
for (item e : S)
{
e += item(c, v);
if (e.weight > w) continue;
if (update(e.weight, e.value))
{
T.push_back(e);
maximize(res, e.value);
}
}
for (const item &e : T)
S.push_back(e);
cout << res << '\n';
}
return 0;
}
Recursive Approach - O(min(W, 2^N)) time - O(N) space#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>
using namespace std;
void file(const string FILE = "Test")
{
freopen((FILE + ".INP").c_str(), "r", stdin);
freopen((FILE + ".OUT").c_str(), "w", stdout);
}
char __;
template<typename T>
void getUnsign(T &x)
{
while (__ = getchar(), __ < '0' || __ > '9');
x = (__ - '0');
while (__ = getchar(), __ >= '0' && __ <= '9')
x = (x << 3) + (x << 1) + (__ - '0');
}
template<typename T>
void getSigned(T &x)
{
while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
bool sign(__ == '-');
if (sign) __ = getchar();
x = (__ - '0');
while (__ = getchar(), __ >= '0' && __ <= '9')
x = (x << 3) + (x << 1) + (__ - '0');
if (sign) x = -x;
}
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;
const int LIM = 25;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int n;
ll w;
ll c[LIM], v[LIM];
ll solve(int i, ll s)
{
if (s < 0) return -LINF;
if (i == 0) return 0;
ll res = 0;
maximize(res, solve(i - 1, s));
maximize(res, solve(i - 1, s - c[i]) + v[i]);
return res;
}
int main()
{
cin >> n >> w;
for (int i = 1; i <= n; ++i)
{
cin >> c[i] >> v[i];
cout << solve(i, w) << '\n';
}
return 0;
}
Recursive Approach with optimization - O(min(W, 2^N / 2^K)) time - O(N) space#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>
using namespace std;
void file(const string FILE = "Test")
{
freopen((FILE + ".INP").c_str(), "r", stdin);
freopen((FILE + ".OUT").c_str(), "w", stdout);
}
char __;
template<typename T>
void getUnsign(T &x)
{
while (__ = getchar(), __ < '0' || __ > '9');
x = (__ - '0');
while (__ = getchar(), __ >= '0' && __ <= '9')
x = (x << 3) + (x << 1) + (__ - '0');
}
template<typename T>
void getSigned(T &x)
{
while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
bool sign(__ == '-');
if (sign) __ = getchar();
x = (__ - '0');
while (__ = getchar(), __ >= '0' && __ <= '9')
x = (x << 3) + (x << 1) + (__ - '0');
if (sign) x = -x;
}
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;
const int LIM = 25;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int n;
ll w;
ll c[LIM], psc[LIM];
ll v[LIM], psv[LIM];
ll solve(int i, ll s)
{
if (s >= psc[i]) return psv[i];
if (s < 0) return -LINF;
if (i == 0) return 0;
ll res = 0;
maximize(res, solve(i - 1, s));
maximize(res, solve(i - 1, s - c[i]) + v[i]);
return res;
}
int main()
{
cin >> n >> w;
psc[0] = psv[0] = 0;
for (int i = 1; i <= n; ++i)
{
cin >> c[i] >> v[i];
psc[i] = psc[i - 1] + c[i];
psv[i] = psv[i - 1] + v[i];
cout << solve(i, w) << '\n';
}
return 0;
}
- E) Meet in the middle approach: On the progress...
B) Solution for small sum of weight — C[i]
- A) Recursive Dynamic Programming:
What have changed from the orginal ?Let $$$f[0][s]$$$ be the end state instead of $$$f[n][w]$$$
Convert the transistion to $$$magic(i, s) \rightarrow magic(i - 1, s)$$$
For the $$$ith$$$ item, the answer right now is $$$magic(i, s)$$$ and here we done
O(NW) time - O(NW) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXW = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
if (s > w) return -LINF; /// Using too much weight
if (i == 0) return 0; /// No available item to add into the bag
ll &res = f[i][s];
if (res != -1) return res;
maximize(res, magic(i - 1, s + 0) + 0); /// Not using this item
maximize(res, magic(i - 1, s + c[i]) + v[i]); /// Using this item
return res;
}
int main()
{
memset(f, -1, sizeof(f));
cin >> n >> w;
for (int i = 1; i <= n; ++i)
{
cin >> c[i] >> v[i];
cout << magic(i, 0) << '\n';
}
return 0;
}
- B) Iterative Dynamic Programming:
What have changed from the orginal ?Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.
The answer is ofcourse $$$f[i][w]$$$ — upto the $$$ith$$$ item
O(NW) time - O(NW) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
ll f[n + 1][w + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i)
{
int c, v;
cin >> c >> v;
for (int s = 1; s <= w; ++s)
{
f[i][s] = max(f[i][s - 1], f[i - 1][s]);
if (s >= c)
{
maximize(f[i][s], f[i - 1][s - c] + v);
}
}
cout << f[i][w] << '\n';
}
return 0;
}
- C) Iterative Dynamic Programming (Space Optimization):
What have changed from the orginal ?Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.
The answer is ofcourse $$$f[w]$$$ — upto the $$$ith$$$ item
O(NW) time - O(W) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int main()
{
int n, w;
cin >> n >> w;
ll f[w + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i)
{
int c, v;
cin >> c >> v;
for (int s = w; s >= c; --s)
maximize(f[s], f[s - c] + v);
cout << f[w] << '\n';
}
return 0;
}
C) Solution for small sum of value — V[i]
- A) Recursive Dynamic Programming:
What have changed from the orginal ?Let $$$f[0][s]$$$ be the end state instead of $$$f[n][w]$$$
Convert the transistion to $$$magic(i, s) \rightarrow magic(i - 1, s)$$$
For the $$$ith$$$ item, the answer right now is $$$result = max(k\ |\ magic(i, k) \leq w$$$
Break the loop after the answer each query is found
O(NSUM) time - O(NSUM) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXSUM = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXSUM];
ll magic(int i = 1, int s = 0)
{
if (s < 0) return +LINF;
if (i == 0) return (s == 0) ? 0 : +LINF;
ll &res = f[i][s];
if (res != -1) return res;
res = +LINF;
minimize(res, magic(i - 1, s - 0) + 0);
minimize(res, magic(i - 1, s - v[i]) + c[i]);
return res;
}
int main()
{
cin >> n >> w;
int sum = 0;
memset(f, -1, sizeof(f));
for (int i = 1; i <= n; ++i)
{
cin >> c[i] >> v[i];
sum += v[i];
for (int res = sum; res >= 0; --res)
{
if (magic(i, res) <= w)
{
cout << res << '\n';
break;
}
}
}
return 0;
}
- B) Iterative Dynamic Programming:
What have changed from the orginal ?Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.
Declare the dp array globally with limit size
The answer is ofcourse $$$res = max(k\ |\ f[i][k]) \leq w$$$ — upto the $$$ith$$$ item
Break the loop after the answer each query is found
O(NSUM) time - O(NSUM) space#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int LIMN = 100;
const int LIMSUM = 1e5 + 15;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
ll f[LIMN][LIMSUM];
int main()
{
int n, w;
cin >> n >> w;
memset(f, +LINF, sizeof(f));
f[0][0] = 0;
int sum = 0;
for (int i = 1; i <= n; ++i)
{
int c, v;
cin >> c >> v;
sum += v;
for (int s = sum; s >= 0; --s)
{
f[i][s] = f[i - 1][s];
if (s >= v)
{
minimize(f[i][s], f[i - 1][s - v] + c);
}
}
for (int res = sum; res >= 0; --res)
{
if (f[i][res] <= w)
{
cout << res << '\n';
break;
}
}
}
return 0;
}
- C) Iterative Dynamic Programming (Space Optimization):
What have changed from the orginal ?Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.
Declare the dp array globally with limit size
The answer is ofcourse $$$res = max(k\ |\ f[k]) \leq w$$$ — upto the $$$ith$$$ item
Break the loop after the answer each query is found
O(NSUM) time - O(NSUM) space#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const int LIM = 1e6 + 16;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
ll f[LIM];
int main()
{
int q, w;
cin >> q >> w;
memset(f, +LINF, sizeof(f));
f[0] = 0;
int sum = 0;
while (q-->0) /// For each query
{
int c, v;
cin >> c >> v;
sum += v;
for (int s = sum; s >= v; --s)
minimize(f[s], f[s - v] + c);
for (int res = sum; res >= 0; --res)
{
if (f[res] <= w)
{
cout << res << '\n';
break;
}
}
}
return 0;
}
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
IX. Optimizations and Heuristic
How to improve the algorithm faster, shorter, simpler, safetier or saving space
A) Filtering the array
- 1) Split items into 2 types, whose weight less than $$$W$$$ and the rest
Hint - All items whose weight bigger than the bag limit will be ignored
- All items whose weight equal the bag limit, we have the max value $$$V_1$$$
- All items whose weight less than the bag limit, we calculate it like above and have the max value $$$V_2$$$
- The result will be $$$res = max(V_1, V_2)$$$
- Highly effective for $$$type\ III$$$ knapsack whose testcases randomly generated that item weight can be much bigger than bag limit
- Less effective in normal testcases
Hint - Lets $$$F(C_p, V_p) = $$$ number of existance of $$$(C_p, V_p)$$$ in the array
- Array with $$$F(C_p, V_p) = X > 2$$$ and $$$F(2C_p, 2V_p) = Y$$$ can be converted to $$$F(C_p, V_p) = X - 2$$$ and $$$F(2C_p, 2V_p) + 1)$$$ without changing the result
- Significant effective for testcases having many duplicated items in arrays
- Having the same idea. Significant effective when $$$\underset{p = 1}{\overset{n}{\Sigma}} C_p \approx X$$$ we can have only $$$O(\sqrt{X})$$$ unique weight, no item whose weight is $$$C$$$ appeared more than twice
- Having the same idea. Significant effective when $$$\underset{p = 1}{\overset{n}{\Sigma}} C_p \approx X$$$ we can have only $$$O(\sqrt{X})$$$ unique value, , no item whose value is $$$V$$$ appeared more than twice
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
X. Debugging
Support you when you are in a trouble that you cant find your bug
A) Wrong answer
1) Becareful when weight sum and value sum is big, it would cause overflow
Debuglong long weight = 0;
long long value = 0;
2) Becareful that in Meet-in-the-middle approach:
You have to update the bitmask that have maxvalue.
You have to update the $$$maxval$$$ and $$$maxmask$$$ before assign $$$x.maxval$$$, $$$x.maxmask$$$
You have to use also in collecting the result
Wrong ll maxval = 0;
for (Node &x : Sr)
{
/// What if x.value > maxval ??
x.maxval = maxval;
x.maxmask = maxmask;
if (maxval < x.value)
{
maxval = x.value;
/// not update maxmask ?
}
}
Wrong if (res < x.value + y.value) /// where is maxvalue ?
{
res = x.value + y.value;
mask_l = y.mask;
mask_r = x.mask;
}
Wrong if (res < x.maxval + y.value)
{
res = x.maxval + y.value;
mask_l = y.mask;
mask_r = x.mask; /// this mask might not given the maxval !
}
Debug ll maxval = 0;
int maxmask = 0;
for (Node &x : Sr)
{
if (maxval < x.value)
{
maxval = x.value;
maxmask = x.mask;
}
x.maxval = maxval;
x.maxmask = maxmask;
}
Debug
if (res < x.maxval + y.value)
{
res = x.maxval + y.value;
mask_l = y.mask;
mask_r = x.maxmask;
}
- 3) Forget base cases: In type $$$IV$$$ the DP is already init as 0, so you dont need the loop to zero, while the $$$V$$$ is not like that when you init it as $$$+oo$$$
Wrong```cpp memset(f, +LINF, sizeof(f)); f[0][0] = 0;
int sum = 0;
for (int i = 1; i <= n; ++i)
{
int c, v;
cin >> c >> v;
sum += v;
for (int s = sum; s >= 1; --s) /// you have to make a loop from s = sum -> 0
{
f[i][s] = f[i - 1][s];
if (s >= v)
{
minimize(f[i][s], f[i - 1][s - v] + c);
}
}
for (int res = sum; res >= 0; --res)
{
if (f[i][res] <= w)
{
cout << res << '\n';
break;
}
}
}
B) Time Limit Exceed
1) Global variable $$$\neq$$$ Local variable
- In Meet-in-the-middle approach, the
solve()
function didnt use global variable (n), it use $$$n = |c| = |s|$$$.
DebugAssign this at the head of the function
void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
int n = c.size(); /// Important !!!
...
}
or
void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
int n = v.size(); /// Important !!!
...
}
2) Forget to use memorization
Wrongll magic(int i = 1, int s = 0)
{
if (s < 0) return +LINF;
if (i > n) return (s == 0) ? 0 : +LINF;
ll res = f[i][s]; /// is should be &res = [i][s]
if (res != -1) return res;
ll res = +LINF;
minimize(res, magic(i + 1, s - 0) + 0);
minimize(res, magic(i + 1, s - v[i]) + c[i]);
return res;
}
Wrongll magic(int i = 1, int s = 0)
{
if (s < 0) return +LINF;
if (i > n) return (s == 0) ? 0 : +LINF;
ll res = +LINF;
minimize(res, magic(i + 1, s - 0) + 0);
minimize(res, magic(i + 1, s - v[i]) + c[i]);
return f[i][s] = res; /// It is calculated first then assigning dp value
}
3) You might get WA if you have wrong initalization or leave the value generated randomly
Wrong ll f[sum + 1];
/// What if f[x > 0] negative ?
f[0] = 0;
for (int i = 1; i <= n; ++i)
for (int s = sum; s >= v[i]; --s)
minimize(f[s], f[s - v[i]] + c[i]);
4) If you wanna binary search for the result, remember that you cant do Prefixmin DP $$$O(N \times SUM)$$$ as what it like in Prefixmax DP $$$O(N \times W)$$$
Wrong
ll f[n + 1][sum + 1];
memset(f, +LINF, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; ++i)
{
for (int s = 1; s <= sum; ++s)
{
f[i][s] = min(f[i][s - 1], f[i - 1][s]);
if (s >= v[i])
{
minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);
}
}
}
int res = 0;
for (int l = 1, r = sum; l <= r; )
{
int m = (l + r) >> 1;
if (f[n][m] <= w)
{
res = m;
l = m + 1;
}
else
{
r = m - 1;
}
}
cout << res;
C) Memory limit exceed
1) Though Meet-in-the-middle approach is faster than Bitmasking Approach, it requires large amount of space — $$$O(2^{^{\frac{n}{2}}})$$$, which may give you MLE !
2) In some cases you will need space optimization if the limit is too tight !
3) Becareful in tracing results
Wrong vector<int> selected;
for (int i = n, s = w; i >= 1 && s >= 1; )
{
if (f[i][s] == f[i - 1][s - c[i]] + v[i])
{
selected.push_back(i);
i -= 1;
s -= c[i];
}
if (f[i][s - 1] > f[i - 1][s])
{
--s;
}
else /// f[i][s] = f[i - 1][s]
{
--i;
}
}
Fixed vector<int> selected;
for (int i = n, s = w; i >= 1 && s >= 1; )
{
if (f[i][s] == f[i - 1][s - c[i]] + v[i])
{
selected.push_back(i);
s -= c[i]; /// This first then decrease (i)
i -= 1;
continue; /// <--- Important in this case
}
if (f[i][s - 1] > f[i - 1][s])
{
--s;
}
else /// f[i][s] = f[i - 1][s]
{
--i;
}
}
D) Runtime Error
1) Out of bound
Wrongll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
if (i > n) return (s <= w) ? 0 : -LINF; /// No available item to add into the bag
ll &res = f[i][s]; /// what if (s > w) ?
if (res != -1) return res;
maximize(res, magic(i + 1, s + 0) + 0); /// Not using this item
maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item
return res;
}
Wrong ll f[n + 1][w + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i)
for (int s = w; s >= 0; --s)
f[i][s] = max(f[i - 1][s], f[i - 1][s - c[i]] + v[i]); /// What if s < c[i] ?
2) Array too big in main function: Declare it globally with the init size bigger than problem constraint a bit
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
XI. Knapsack Variation and Practice Problems
In case you need a place to practice or submitting
NoteThe statement is in Italian Language
Translated into English: Given an array of length $$$N$$$, find the smallest sum $$$\geq K$$$ of a subset.
Limitation: $$$N,K \leq 5000 , a_i \leq 10^6$$$
HintKeep adding the items from largest to smallest until they dont fit in the knapsack
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
Teleporter: [Previous] | | | [Next]
XII. Blog status
The current progress and contributor of this blogs
Sorry for being annoyed but for somewhat the reason that
Update the blog with better version: Error
Update the blog with a half then reupdate with better version: Error
Update the blog with nothing then reupdate with better version: Error
Update the blog little by little, view first then publish: Updated or Error
Draft the blog, and do the same things like above: Error
Draft the blog then make a new blog for better version: Ok
SPyofgame coach when
Really good tutorial about various methods to solve this problems. seems highly underrated to me.
This blog is so underrated!
it actually is
Is the judge for Bài toán ba lô 3 broken or something?
According to the translation, the problem statement asks me to print "The first line should print the number of items CJ takes to maximize the total value. The second line should print the indices of the selected items in increasing order."
But doing that i get wrong answer and it looks like the judge answer is aparantly one number? Like what is even hapenning?
Edit: Got it to work. The Judge interface for the OJ was very weird so it caught me off-guard. The problem is as stated in the question. My code's problem was that I had weight as int in my node struct, while I was calling the constructor using a long long variable. So it caused some bugs. Here's my solution: https://ideone.com/2LxqbY
Great blog.
why only 7 upvotes :(