fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <ctime>
  4.  
  5. typedef struct{
  6. 	int size;
  7. 	int val;
  8. } Item;
  9.  
  10. const int n = 10;	// Число предметов
  11. const int m = 50;	// Емкость рюкзака
  12. Item items[n];
  13. int max_known[n];
  14. Item item_known[n];
  15.  
  16. int knap(int cap){
  17. 	int space;
  18. 	int max;
  19. 	int maxi;
  20. 	int t;
  21.  
  22. 	if(max_known[cap] != -1) return max_known[cap];
  23. 	for(int i = 0, max = 0; i < n; i++)
  24. 		if((space = cap - items[i].size) >= 0)
  25. 			if((t = knap(space) + items[i].val) > max){
  26. 				max = t;
  27. 				maxi = i;
  28. 			}
  29. 	max_known[cap] = max;
  30. 	item_known[cap] = items[maxi];
  31. 	return max;
  32. }
  33.  
  34.  
  35. int main(){
  36. 	std::memset(max_known, -1, n * sizeof(int));
  37.  
  38. 	// Создаем рандомные вещи
  39. 	std::srand(time(NULL));
  40. 	for(int i = 0; i < n; i++){
  41. 		Item it;
  42. 		it.size = 1 + std::rand() % 15;
  43. 		it.val = 1 + std::rand() % 701;
  44. 		items[i] = it;
  45. 	}
  46.  
  47. 	std::cout << knap(m) << std::endl;
  48.  
  49. 	int pause;
  50. 	std::cin >> pause;
  51. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/maei6Q
language:
C++14 (gcc 8.3)
created:
9 years 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!