fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. class Knapsack{
  6. private:
  7. 	vector<int> weights;
  8. 	vector<int> values;
  9. 	int n, w;
  10. 	//int **v;
  11. 	vector< vector<int> > v;
  12. public:
  13. 	Knapsack(vector<int> wt, vector<int> val, int n, int cap){
  14. 		// Сохранение переданных векторов, числа элементов и вместимости ранца
  15. 		weights.assign(wt.begin(), wt.end());
  16. 		values.assign(val.begin(), val.end());
  17. 		this->n = n;
  18. 		this->w = cap;
  19. 		// Создание таблицы мемоизации и заполнение начальными значениями
  20. 		/*v = new int * [n];
  21. 		for(int i = 0; i < n; i++)
  22. 			v[i] = new int [w];*/
  23. 		vector< vector<int> > tmp(n, vector<int>(w));
  24. 		v.assign(tmp.begin(), tmp.end());
  25. 		// Инициализирование таблицы
  26. 		for(int i = 0; i < n; i++)
  27. 			for(int j = 0; j < w; j++)
  28. 				v[i][j] = -1;
  29. 		// Инициализирование нулями первой строки и первого столбца
  30. 		for(int i = 0; i < w; i++)
  31. 			v[0][i] = 0;
  32. 		for(int i = 0; i < n; i++)
  33. 			v[i][0] = 0;
  34. 	}
  35. 	~Knapsack(){
  36. 		//for(int i = 0; i < n; i++)
  37. 		//	delete[] v[i];
  38. 		//delete[] v;
  39. 	}
  40.  
  41. 	int knapsack_solver(int i, int j);
  42. 	int solve();
  43. };
  44.  
  45. int Knapsack::knapsack_solver(int i, int j){
  46. 	int value;
  47. 	if(v[i][j] < 0){
  48. 		if(j < weights[i])
  49. 			value = knapsack_solver(i - 1, j);
  50. 		else
  51. 			value = max(knapsack_solver(i - 1, j),
  52. 						values[i] + knapsack_solver(i - 1, j - weights[i]));
  53. 		v[i][j] = value;
  54. 	}
  55. 	return v[i][j];
  56. }
  57.  
  58. int Knapsack::solve(){
  59. 	return knapsack_solver(n, w);
  60. }
  61.  
  62. int main(){
  63. 	int n = 4, cap = 5;
  64. 	int w[4] = {2, 1, 3, 2};
  65. 	int v[4] = {12, 10, 20, 15};
  66. 	vector<int> wt(w, w + 4);
  67. 	vector<int> val(v, v + 4);
  68.  
  69. 	Knapsack knap(wt, val, n, cap);
  70. 	cout << knap.solve() << endl;
  71.  
  72. 	int pause;
  73. 	cin >> pause;
  74.  
  75. 	return 0;
  76. }
Runtime error #stdin #stdout 0s 3412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KmRwtc
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!