Maximum Amount of Gold

Task. Given n gold bars, find the maximum weight of gold that fits into a bag of capacity W. 

Input Format: The first line of the input contains the capacity W of a knapsack and the number n of bars of gold. The next line contains n integers w0,w1,...,wn−1 defining the weights of the bars of gold. 

Constraints: 1 ≤ W ≤ 104; 1 ≤ n ≤ 300; 0 ≤ w0,...,wn−1 ≤ 105. 

Output Format: Output the maximum weight of gold that fits into a knapsack of capacity W.

#include <iostream>
#include <vector>
#include<algorithm>

using std::vector;

int optimal_weight(int W, const vector<int> &v) {
  //write your code here
  vector< vector<int> > w(v.size()+1,vector<int>(W+1));
  
  int current_weight = 0;
  
  for (int i = 1; i <=v.size();++i) {
     for(int k=1;k<=W;++k)
     {
     	w[i][k]=w[i-1][k];
     	if(v[i-1]<=k)
       w[i][k]=std::max(w[i-1][k-v[i-1]]+v[i-1],w[i][k]);
     
	}
  }
  return w[v.size()][W];
  
}

int main() {
  int n, W;
  std::cin >> W >> n;
  vector<int> w(n);
  for (int i = 0; i < n; i++) {
    std::cin >> w[i];
  }
  std::cout << optimal_weight(W, w) << '\n';
  
}