fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> berat(102);
  5. vector<int> harga(102);
  6. int b;
  7. int dp[2002][102];
  8.  
  9. int f(int a, int z) {
  10.     if (z == b+1 || a == 0)
  11.         return 0;
  12.  
  13. 	if (dp[a][z] == -1) {
  14. 		dp[a][z] = f(a, z+1);
  15. 		if (a >= berat[z]) {
  16. 			int pilih = harga[z] + f(a - berat[z], z+1);
  17. 			dp[a][z] = max(dp[a][z], pilih);
  18. 		}
  19. 	}
  20.  
  21. 	return dp[a][z];
  22. }
  23.  
  24. int main() {
  25. 	memset(dp, -1, sizeof dp);
  26.     int a;
  27.     cin >> a >> b;
  28.  
  29.     for (int i = 1; i <= b; i++) {
  30.         cin >> berat[i] >> harga[i];
  31.     }
  32.  
  33. 	int teringan = a;
  34. 	for (int i = 0; i <= a; i++) {
  35. 		if (f(i, 1) == f(a, 1)) {
  36. 			teringan = i;
  37. 			break;
  38. 		}
  39. 	}
  40.     for (int i = 1; i <= b; i++) {
  41.     	if (teringan >= berat[i] && f(teringan, i) == f(teringan - berat[i], i+1) + harga[i]) {
  42.     		cout << i << '\n';
  43.     		teringan -= berat[i];
  44.     	}
  45.     }
  46.  
  47.     return 0;
  48. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
30 3 
10 1
15 2
25 3
stdout 
1
2
https://ideone.com/uYi78I
language:
C++ (gcc 8.3)
created:
13 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!