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