fork download

copy

#include <iostream>
#include <vector>
using namespace std;
 
 
class Knapsack{
private:
	vector<int> weights;
	vector<int> values;
	int n, w;
	//int **v;
	vector< vector<int> > v;
public:
	Knapsack(vector<int> wt, vector<int> val, int n, int cap){
		// Сохранение переданных векторов, числа элементов и вместимости ранца
		weights.assign(wt.begin(), wt.end());
		values.assign(val.begin(), val.end());
		this->n = n;
		this->w = cap;
		// Создание таблицы мемоизации и заполнение начальными значениями
		/*v = new int * [n];
		for(int i = 0; i < n; i++)
			v[i] = new int [w];*/
		v = vector<n, vector<int>(w));
		// Инициализирование таблицы
		for(int i = 0; i < n; i++)
			for(int j = 0; j < w; j++)
				v[i][j] = -1;
		// Инициализирование нулями первой строки и первого столбца
		for(int i = 0; i < w; i++)
			v[0][i] = 0;
		for(int i = 0; i < n; i++)
			v[i][0] = 0;
	}
	~Knapsack(){
		//for(int i = 0; i < n; i++)
		//	delete[] v[i];
		//delete[] v;
	}
 
	int knapsack_solver(int i, int j);
	int solve();
};
 
int Knapsack::knapsack_solver(int i, int j){
	int value;
	if(v[i][j] < 0){
		if(j < weights[i])
			value = knapsack_solver(i - 1, j);
		else
			value = max(knapsack_solver(i - 1, j),
						values[i] + knapsack_solver(i - 1, j - weights[i]));
		v[i][j] = value;
	}
	return v[i][j];
}
 
int Knapsack::solve(){
	return knapsack_solver(n, w);
}
 
int main(){
	int n = 4, cap = 5;
	int w[4] = {2, 1, 3, 2};
	int v[4] = {12, 10, 20, 15};
	vector<int> wt(w, w + 4);
	vector<int> val(v, v + 4);
 
	Knapsack knap(wt, val, n, cap);
	cout << knap.solve() << endl;
 
	int pause;
	cin >> pause;
 
	return 0;
}

prog.cpp: In constructor 'Knapsack::Knapsack(std::vector<int>, std::vector<int>, int, int)':
prog.cpp:24:30: error: temporary of non-literal type 'std::vector<int>' in a constant expression
   v = vector<n, vector<int>(w));
                              ^
In file included from /usr/include/c++/5/vector:64:0,
                 from prog.cpp:2:
/usr/include/c++/5/bits/stl_vector.h:214:11: note: 'std::vector<int>' is not literal because:
     class vector : protected _Vector_base<_Tp, _Alloc>
           ^
/usr/include/c++/5/bits/stl_vector.h:214:11: note:   'std::vector<int>' has a non-trivial destructor
prog.cpp:24:30: error: type/value mismatch at argument 1 in template parameter list for 'template<class _Tp, class _Alloc> class std::vector'
   v = vector<n, vector<int>(w));
                              ^
prog.cpp:24:30: note:   expected a type, got 'n'
prog.cpp:24:30: error: type/value mismatch at argument 2 in template parameter list for 'template<class _Tp, class _Alloc> class std::vector'
prog.cpp:24:30: note:   expected a type, got 'std::vector<int>(((std::vector<int>::size_type)((Knapsack*)this)->Knapsack::w), std::allocator<int>())'

Standard output is empty