• Source 
    1. #include <iostream>
    2. #include <math.h>
    3. #include <stdio.h>
    4. #include <algorithm>
    5. #include <vector>
    6. using namespace std;
    7.  
    8. struct data
    9. {
    10. 	int W, V;
    11. } typedef data;
    12. int N;
    13. int M;
    14. data Gold1 [45];
    15. data Gold2 [45];
    16. int SMax;
    17. int S[1300006];
    18.  
    19. int cmp (data a, data b)
    20. {
    21. 	if (a.W>=b.W) return 0;
    22. 	return 1;
    23. }
    24.  
    25. vector <data> P1;
    26. vector <data> P2;
    27.  
    28. int N1, N2;
    29. data tmp;
    30. void sinh1 (int u, int W, int V)
    31. {
    32. 	if (W>M) return;
    33. 	if (u==N1+1)
    34. 	{
    35. 		tmp.W=W;
    36. 		tmp.V=V;
    37. 		P1.push_back (tmp);
    38. 		return;
    39. 	}
    40. 	else
    41. 	{
    42. 		sinh1 (u+1, W, V);
    43. 		sinh1 (u+1, W+Gold1[u].W, V+Gold1[u].V);
    44. 	}
    45. }
    46.  
    47. void sinh2 (int u, int W, int V)
    48. {
    49. 	if (W>M) return;
    50. 	if (u==N2+1)
    51. 	{
    52. 		tmp.W=W;
    53. 		tmp.V=V;
    54. 		P2.push_back (tmp);
    55. 		return;
    56. 	}
    57. 	else
    58. 	{
    59. 		sinh2 (u+1, W, V);
    60. 		sinh2 (u+1, W+Gold2[u].W, V+Gold2[u].V);
    61. 	}
    62. }
    63.  
    64.  
    65. int BS (int front, int back, int x)
    66. {
    67. 	int vt=-1;
    68. 	while (front<=back)
    69. 	{
    70. 		int mid = (front+back)/2;
    71. 		if (P2[mid].W<=x)
    72. 		{
    73. 			front=mid+1;
    74. 			vt=mid;
    75. 		} else back=mid-1;
    76. 	}
    77. 	return vt;
    78. }
    79.  
    80. int main ()
    81. {
    82. 	scanf ("%d%d", &N, &M);
    83.  
    84. 	N2=N/2;
    85. 	N1=N-(N/2);
    86.  
    87. 	for (int i=1; i<=N1; i++)
    88. 	{
    89. 		scanf ("%d%d", &Gold1[i].W, &Gold1[i].V);
    90. 	}
    91. 	for (int i=1; i<=N2; i++)
    92. 	{
    93. 		scanf ("%d%d", &Gold2[i].W, &Gold2[i].V);
    94. 	}
    95.  
    96. 	//Tim truong hop:
    97. 	sinh1 (1, 0, 0);
    98. 	sinh2 (1, 0, 0);
    99. 	sort (P2.begin(), P2.end(), cmp);
    100.  
    101. 	int Ans=0;
    102. 	S[0]=P2[0].V;
    103. 	for (int i=1; i<P2.size(); i++)
    104. 	{
    105. 		S[i]=max (S[i-1], P2[i].V);
    106. 		Ans = max (Ans, P2[i].V);
    107. 	}
    108. 	for (int i=0; i<P1.size (); i++)
    109. 	{
    110. 		int VT = BS (0, P2.size()-1, M-P1[i].W);
    111. 		if (VT!=-1)
    112. 		{
    113. 			Ans = max (Ans, S[VT]+P1[i].V);
    114. 		}
    115. 		Ans = max (Ans, P1[i].V);
    116. 	}
    117. 	printf ("%d", Ans);
    118. 	return 0;
    119. }