-
Notifications
You must be signed in to change notification settings - Fork 20
/
Copy pathCTDL_003 - PHƯƠNG ÁN TỐI ƯU
78 lines (78 loc) · 2.6 KB
/
CTDL_003 - PHƯƠNG ÁN TỐI ƯU
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
string ans;
vector<pair<int, int>> x;
vector<vector<int>> F;
void trace(int n, int k)
{
if (n == 0)
return;
if (F[n][k] == F[n - 1][k])
trace(n - 1, k);
else
{
trace(n - 1, k - x[n].first);
ans[n - 1] = '1';
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
F.resize((n + 1), vector<int>(k + 1, 0));
x.resize(n + 1);
for (int i = 1; i <= n; i++)
{
ans = ans + "0";
cin >> x[i].second;
}
for (int i = 1; i <= n; i++)
cin >> x[i].first;
for (int i = 0; i <= n; i++)
{
F[i][0] = 0;
F[0][i] = 0;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++)
{
if (j < x[i].first)
F[i][j] = F[i - 1][j];
else
F[i][j] = max(F[i - 1][j], F[i - 1][j - x[i].first] + x[i].second);
}
cout << F[n][k] << endl;
trace(n, k);
for (char i : ans)
cout << i << ' ';
}
/* Do Xuan Huong
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@##################@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@#############################@@@@@@@@@@@@@@@@
@@@@@@@@@@@@&####################################@@@@@@@@@@@@
@@@@@@@@@@##########################################@@@@@@@@@
@@@@@@@@##############################################@@@@@@@
@@@@@@#################################################@@@@@@
@@@@@####################################################@@@@
@@@%#####################@@@@@@@@@@@######################@@@
@@@###################@@@@@@@@@@@@@@@@@####################@@
@@##################@@@@@@ @@@@@@##################@@
@@#################@@@@@ @@@@###################@
@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@
@ &@@@@ @@@@ .......@@
@@ @@@@@@ @@@@@@ .......@@
@@ @@@@@@@@@@@@@@@@@ .......@@@
@@@ @@@@@@@@@@@ ......@@@@
@@@@ ......@@@@@
@@@@@@ ......@@@@@@
@@@@@@@ .....@@@@@@@@
@@@@@@@@@ .....@@@@@@@@@@
@@@@@@@@@@@@ ....@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@ ....@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@% .@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/