fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. template<typename T>
  9. void maximize(T& a, const T& b) {
  10. 	if (a < b) a = b; 
  11. }
  12.  
  13. const int INF = 1e9;  
  14. const ll LINF = 1e18;  
  15.  
  16. // dp knapsack 
  17. // Bài toán gốc: 
  18. // Cho n món vật và một balo có khối lượng là S, mỗi món vật có 2 tham số là:   
  19. // w(i): khối lượng của món vật thứ i   
  20. // v(i): giá trị của món vật thứ i   
  21. // Yêu cầu chọn ra một số món vật sao cho tổng khối lượng w(i) không vượt quá S và tổng giá trị v(i) là lớn nhất?
  22.  
  23. const int N = 1e2 + 5; 
  24. const int S = 1e5 + 5;    
  25.  
  26. int n, s;  
  27. int w[N], v[N];  
  28.  
  29. ll ans;   
  30. void backtrack(int i, ll sum_w, ll sum_v) { // O(2^n)
  31. 	if (i == n + 1) {
  32. 		ans = max(ans, sum_v);  
  33. 		return; 
  34. 	}
  35.  
  36. 	// Bỏ qua món vật thứ i   
  37. 	backtrack(i + 1, sum_w, sum_v);  
  38.  
  39. 	// Chọn món vật thứ i 
  40. 	if (sum_w + w[i] <= S) {
  41. 		backtrack(i + 1, sum_w + w[i], sum_v + v[i]); 
  42. 	}
  43. }
  44.  
  45. ll dp[N][S]; // dp[i][j] = tổng giá trị v(i) lớn nhất
  46.   			 // 		   khi xét i món vật đầu tiên với tổng khối lượng w(i) của các món vật đã chọn là j 
  47.  
  48. int main() {
  49. 	ios::sync_with_stdio(false); 
  50. 	cin.tie(nullptr);  	
  51. 	cin >> n >> s;  
  52. 	for (int i = 1; i <= n; i++) {
  53. 		cin >> w[i] >> v[i]; 
  54. 	} 
  55.  
  56. 	// ans = -LINF;  
  57. 	// backtrack(1, 0, 0); 
  58. 	// cout << ans << '\n'; 
  59.  
  60. 	for (int i = 0; i <= n; i++) {
  61. 		for (int j = 0; j <= s; j++) dp[i][j] = -LINF; 
  62. 	}
  63. 	dp[0][0] = 0;   
  64.  
  65. 	for (int i = 1; i <= n; i++) {
  66. 		for (int j = 0; j <= s; j++) {
  67. 			// Bỏ qua món vật thứ i 
  68. 			maximize(dp[i][j], dp[i - 1][j]);
  69. 			// Chọn món vật thứ i 
  70. 			if (j >= w[i]) maximize(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
  71. 		}
  72. 	} // O(N * S)
  73.  
  74. 	ll ans = 0;   
  75. 	for (int j = 0; j <= s; j++) {
  76. 		maximize(ans, dp[n][j]); 
  77. 	}
  78.  
  79. 	cout << ans << '\n'; 
  80. }
Success #stdin #stdout 0.01s 5596KB
comments (?)
stdin
copy 
3 8
3 30
4 50
5 60
stdout
copy 
90
https://ideone.com/WOMoQT
language:
C++14 (gcc 8.3)
created:
40 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!