Recipe: AILEARNS KNAPSACK CC++ OVERFLOW

created by Vincera

Profile

• Name: AILEARNS KNAPSACK CC++ OVERFLOW
• ID: 104684
• Shared with: Public
• Parent: None
• Children: None
• Created on: March 24, 2021 at 20:26 PM UTC
• Updated on: December 30, 2024 at 19:56 PM UTC
• Description:

  TEST

Code

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

using namespace std;

using WeightValue = pair<int, int>;
using WeightValueList = vector<WeightValue>;

int main() {

  int knapsack_weight;
  cout << "what's the weight of the knapsack?" << endl;
  cin >> knapsack_weight;

  int number_of_elements;
  cout << "How many elements are you going to enter?" << endl;
  cin >> number_of_elements;

  WeightValueList elements(number_of_elements);

  for (int i = 0; i < number_of_elements; ++i) {
    int w,v;
    cout << "insert the weight of the element" << endl;
    cin >> w;
    cout << "insert the value of the element" << endl;
    cin >> v;
    elements[i] = make_pair(w,v);
  }

  int mat[number_of_elements+1][knapsack_weight+1];

  for (int i = 0; i <= number_of_elements; ++i)
    for (int j = 0; j <=knapsack_weight; ++j)
      mat[i][j] = 0;

  for (int i = number_of_elements-1; i >=0; --i)
    for (int j = 1; j <= knapsack_weight; ++j) {

      int wi = elements[i].first;
      int vi = elements[i].second;

        if (wi <= j) {  // -> check if we can to better for weight j
                          // by try choosing the i-th element
          mat[i][j] = max(vi + mat[i+1][j-wi], mat[i+1][j]);
        } else {          // if the weight of i is too big, then just 
                          //copy the previously found optimum
          mat[i][j] = mat[i+1][j];
        }
    }

  cout << "The maximum value is : " << mat[0][knapsack_weight] << endl;
}