Playground
#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; //weight[i] e tezhinata na i-tiot predmet //value[i] e vrednosta na i-tiot predmet int knapsack(vector<int> &weight, vector<int> &value, int capacity) { int N = weight.size(); //napravi matrica, i postavi se ednakvo na 0 int best[N+1][capacity+1]; memset(best, 0, sizeof(best)); //pochni so razgleduvanje na prviot predmet, pa na prvite dva, itn... for(int x=1; x <= N; x++) { int objectWeight = weight[x - 1]; //bidejki prviot element ima indeks 0 int objectValue = value[x - 1]; //bidejki prviot element ima indeks 0 //razgledaj ranci so razlichen kapacitet... for(int c=0; c <= capacity; c++) { //ako ne go zememe x-tiot predmet int leaveValue = best[x-1][c]; best[x][c] = leaveValue; if(objectWeight <= c) { //predmetot ne e pogolem od ranecot //obidi se da go zemesh... int takeValue = best[x-1][c - objectWeight] + objectValue; if(takeValue > leaveValue) { //podobro reshenie e da go zememe predmetot best[x][c] = takeValue; } } } } return best[N][capacity]; } int main() { vector<int> weight = {9, 5, 3}; vector<int> value = {3000, 2000, 1500}; cout << knapsack(weight, value, 10) << endl; return 0; }
Input data
Program output
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!