Advertisement
HabKaffee

By Dynamic Programming

Oct 31st, 2020
151
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cmath>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <fstream>
  5.  
  6. std::ifstream FileIn("Task.txt");
  7.  
  8. int dynamicAlgorithm(int* arrayOfCost, int* arrayOfWeight, int numberOfItem, int maxWeight) {
  9.     int** array = new int*[numberOfItem];
  10.     for (size_t i = 0; i < numberOfItem; ++i) {
  11.         array[i] = new int[maxWeight];
  12.     }
  13.  
  14.     for (size_t j = 0; j < maxWeight; ++j) {
  15.             array[0][j] = 0;
  16.     }
  17.  
  18.     for (size_t i = 0; i < numberOfItem; ++i) {
  19.         for (size_t j = 0; j < maxWeight; ++j) {
  20.             if (i > 0) {
  21.                 if (j - arrayOfWeight[i] >= 0) {
  22.                     array[i][j] = std::max(arrayOfCost[i] + array[i - 1][j - arrayOfWeight[i]], array[i - 1][j]);
  23.                 }
  24.                 else {
  25.                     array[i][j] = array[i - 1][j];
  26.                 }
  27.             }
  28.             else if (j >= arrayOfWeight[i]) {
  29.                 array[i][j] = arrayOfCost[i];
  30.             }
  31.         }
  32.     }
  33.  
  34.  
  35.     int result = array[numberOfItem - 1][maxWeight - 1];
  36.  
  37.     for (size_t i = 0; i < numberOfItem; ++i) {
  38.         delete[] array[i];
  39.     }
  40.     delete[] array;
  41.  
  42.     return result;
  43. }
  44.  
  45.  
  46. int main() {
  47.     int maxWeight = 0, numberOfItem = 0;
  48.  
  49.     FileIn >> numberOfItem >> maxWeight;
  50.  
  51.     int* arrayOfWeight = new int[numberOfItem];
  52.     int* arrayOfCost = new int[numberOfItem];
  53.  
  54.     for (size_t i = 0; i < numberOfItem; ++i) {
  55.         FileIn >> arrayOfWeight[i];
  56.     }
  57.     for (size_t i = 0; i < numberOfItem; ++i) {
  58.         FileIn >> arrayOfCost[i];
  59.     }
  60.     std::cout << "Max cost is " << dynamicAlgorithm(arrayOfCost, arrayOfWeight, numberOfItem, maxWeight);
  61.  
  62.     delete[] arrayOfCost;
  63.     delete[] arrayOfWeight;
  64.     return 0;
  65. }
  66.  
Advertisement
RAW Paste Data Copied
Advertisement