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