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. const int size = 100;
  13.  
  14. Item items[n];
  15. int max_known[size];
  16. Item item_known[size];
  17.  
  18. int knap(int cap){
  19. 	int space;
  20. 	int max = 0;
  21. 	int maxi = 0;
  22. 	int i, t;
  23.  
  24. 	if(max_known[cap] != -1) return max_known[cap];
  25. 	for(i = 0, max = 0; i < n; i++)
  26. 		if((space = cap - items[i].size) >= 0)
  27. 			if((t = knap(space) + items[i].val) > max){
  28. 				max = t;
  29. 				maxi = i;
  30. 			}
  31. 	max_known[cap] = max;
  32. 	item_known[cap] = items[maxi];
  33. 	return max;
  34. }
  35.  
  36.  
  37. int main(){
  38. 	std::memset(max_known, -1, size * sizeof(int));
  39.  
  40. 	// Создаем рандомные вещи
  41. 	std::srand(time(NULL));
  42. 	for(int i = 0; i < n; i++){
  43. 		Item it;
  44. 		it.size = 1 + std::rand() % 15;
  45. 		it.val = 1 + std::rand() % 701;
  46. 		items[i] = it;
  47. 	}
  48.  
  49. 	std::cout << knap(m) << std::endl;
  50.  
  51. 	int pause;
  52. 	std::cin >> pause;
  53. }
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
18800
https://ideone.com/mQbUJn
language:
C++14 (gcc 8.3)
created:
8 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!