fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int N, kapasitas, berat[101], harga[101];
  5. int memo[2002][101];
  6.  
  7. int knapsack(int bobot, int n) {
  8. 	if(n == N)
  9. 		return 0;
  10. 	if(memo[bobot][n] != -1)
  11. 		return memo[bobot][n];
  12.  
  13. 	// skip
  14. 	int best = knapsack(bobot, n+1);
  15. 	// ambil
  16. 	if(bobot+berat[n] <= kapasitas)
  17. 		best = max(best, knapsack(bobot+berat[n], n+1)+harga[n]);
  18. 	return memo[bobot][n] = best;
  19. }
  20.  
  21. int main() {
  22. 	cin >> kapasitas >> N;
  23. 	for(int i = 0; i < N; i++)
  24. 		cin >> berat[i] >> harga[i];
  25. 	memset(memo, -1, sizeof(memo));
  26.  
  27. 	// top down
  28. 	// cout << knapsack(0, 0) << endl;
  29.  
  30. 	// bottom up
  31. 	for(int i = 0; i <= kapasitas; i++)
  32. 		memo[i][0] = 0;
  33.  
  34. 	for(int i = 1; i <= N; i++) {
  35. 		for(int j = 0; j <= kapasitas; j++) {
  36. 			int best = memo[j][i-1];
  37. 			if(j >= berat[i-1])
  38. 				best = max(best, memo[j-berat[i-1]][i-1]+harga[i-1]);
  39. 			memo[j][i] = best;
  40. 		}
  41. 	}
  42. 	cout << memo[kapasitas][N] << endl;
  43.  
  44. 	return 0;
  45. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
11 3
10 30
6 17
5 14
stdout
copy 
31
https://ideone.com/214sFJ
language:
C++ (gcc 8.3)
created:
16 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!