fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6. 	int n, k;
  7. 	scanf("%d%d", &n, &k);
  8. 	int w[k+1], h[k+1];
  9. 	for (int i = 1; i <= k; i++) {
  10. 		scanf("%d%d", &w[i], &h[i]);
  11. 	}
  12. 	int dp[k+2][n+1];
  13. 	for (int i = 0; i <= n; i++) {
  14. 		dp[k+1][i] = 0;
  15. 	}
  16. 	for (int i = k; i >= 1; i--) {
  17. 		for (int j = 0; j <= n; j++) {
  18. 			dp[i][j] = dp[i+1][j];
  19. 			if (j >= w[i]) {
  20. 				dp[i][j] = max(dp[i][j], dp[i+1][j-w[i]] + h[i]);
  21. 			}
  22. 		}
  23. 	}
  24. 	int teringan;
  25. 	for (int i = n; i >= 0; i--) {
  26. 		if (dp[1][n] == dp[1][i]) {
  27. 			teringan = i;
  28. 		}
  29. 	}
  30. 	for (int i = 1; i <= k; i++) {
  31. 		if (dp[i][teringan] == dp[i+1][teringan-w[i]] + h[i]) {
  32. 			printf("%d\n", i);
  33. 			teringan -= w[i];
  34. 		}
  35. 	}
  36. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
30 3 
10 1
15 2
25 3
stdout 
1
2
https://ideone.com/zktxpu
language:
C++ (gcc 8.3)
created:
15 days ago
visibility:
public

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!