-
Notifications
You must be signed in to change notification settings - Fork 0
/
E_-_Knapsack_2.cpp
57 lines (57 loc) · 1.08 KB
/
E_-_Knapsack_2.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// हर हर महादेव
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
vector<ll> wgt, val;
vector<vector<ll>> dp(102, vector<ll>(100002, -1));
bool f(ll n, ll sm, ll w)
{
// Base
// if (w < 0)
// return 0;
if (n == 0)
{
if (sm == 0)
return 1;
else
return 0;
}
// if (sm == 0)
// return 1;
if (dp[n][sm] != -1)
{
if (dp[n][sm])
return 1;
return 0;
}
// Recursive
bool r1 = 0, r2 = 0;
if (sm - val[n - 1] >= 0 && w - wgt[n - 1] >= 0)
r1 = f(n - 1, sm - val[n - 1], w - wgt[n - 1]);
r2 = f(n - 1, sm, w);
if (r1 | r2)
dp[n][sm] = 1;
dp[n][sm] = 0;
return (r1 | r2);
}
int main()
{
ll n, w;
cin >> n >> w;
ll n1 = n, sm = 0;
while (n--)
{
ll w, v;
cin >> w >> v;
wgt.push_back(w);
val.push_back(v);
sm += v;
}
ll mx = 0;
for (ll i = 1; i <= sm; i++)
{
if (f(n1, i, w))
mx = i;
}
cout << mx << "\n";
}