tests

6
4
1 2 3 6

8
2
5 4


1000
12
250 1 2 5 250 250 8 250 1000 1000 125 125

Решение задачи о 0-1-рюкзаке за псевдополиномиальное время.

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

typedef std::vector<std::vector<int> > Table;

void GetInput(int *targetValue, std::vector<int> *values) {
  std::cin >> *targetValue;
  int valuesCount;
  std::cin >> valuesCount;
  values->resize(valuesCount + 1);
  for(size_t index = 1; index < values->size(); ++index) {
    std::cin >> values->at(index);
  }
}

void ResizeTable(size_t width, size_t height,
                 Table *table) {
  table->resize(height);
  for(size_t index = 0; index < table->size(); ++index) {
    table->at(index).resize(width);
  }
}

void OutputValuesRecursion(const std::vector<int> &values,
                           const Table &table,
                           int usingFirst, int currentValue) {
  if(table[usingFirst][currentValue] == 0) {
    return;
  }

  if(table[usingFirst - 1][currentValue] ==
     table[usingFirst][currentValue]) {
    OutputValuesRecursion(values, table,
                          usingFirst - 1, currentValue);
  } else {
    OutputValuesRecursion(values, table,
                          usingFirst - 1,
                          currentValue - values[usingFirst]);

    std::cout << values[usingFirst] << ' ';
  }
}

void OutputValues(const std::vector<int> &values,
                  const Table &table) {
  std::cout << "Разложение: ";
  OutputValuesRecursion(values, table,
                        table.size() - 1,
                        table.front().size() - 1);
  std::cout << "\n";
}

void OutputTable(const Table &table) {
  for(size_t y = 0; y < table.size(); ++y) {
    std::copy(table[y].begin(), table[y].end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
  }
}

int main() {
  std::vector<int> values;
  int targetValue;

  GetInput(&targetValue, &values);

  std::cout << "Задача: Собрать " << targetValue << " из чисел a = {";
  std::copy(values.begin() + 1, values.end(),
            std::ostream_iterator<int>(std::cout, " "));
  std::cout << "}.\n\n";
            
  Table dynamicTable;
  ResizeTable(targetValue + 1, values.size(),
              &dynamicTable);

  // Compute table
  for (size_t index = 0; index < dynamicTable.front().size();
      ++index) {
    dynamicTable[0][index] = 0;
  }

  for (size_t usingFirst = 1; usingFirst < dynamicTable.size();
      ++usingFirst) {
    for (size_t currentValue = 0; currentValue < dynamicTable.front().size();
        ++currentValue) {
      std::cout << "Заполняем ячейку (" << usingFirst << ", " << currentValue << "),\n"
                << "F(" << usingFirst << ", " <<  currentValue << ")\t= max (F(" 
                << usingFirst - 1 << ", " << currentValue << "), " << "F(" 
                << usingFirst - 1 << ", " << currentValue << " - a_" << usingFirst << ") + a_" 
                << usingFirst << ")) \n"
                << "\t = max (" 
                << dynamicTable[usingFirst - 1][currentValue] << ", " << "F(" 
                << usingFirst - 1 << ", " << currentValue << " - " << values[usingFirst]
                << ") + " << values[usingFirst] << ")) \n"
                << "\t = max (" 
                << dynamicTable[usingFirst - 1][currentValue] << ", " 
                << dynamicTable[usingFirst - 1][currentValue - values[usingFirst]] + values[usingFirst] <<  "). \n\n";
      
      dynamicTable[usingFirst][currentValue] = 
        dynamicTable[usingFirst - 1][currentValue];
      if (values[usingFirst] <= currentValue
          && dynamicTable[usingFirst - 1][currentValue - values[usingFirst]] +
          values[usingFirst] > dynamicTable[usingFirst][currentValue]) {
        dynamicTable[usingFirst][currentValue] = 
          dynamicTable[usingFirst - 1][currentValue - values[usingFirst]] +
          values[usingFirst];
      }
      std::cout << "Таблица F на текущем шаге:\n";
      OutputTable(dynamicTable);
      std::cout << "\n";
    }
  }


  if(dynamicTable[values.size() - 1][targetValue] ==
     targetValue) {
    OutputValues(values, dynamicTable);
  } else {
    std::cout << "Невозможно собрать  " << targetValue 
              << " из набора {a}.\n";
  }

  std::cout << std::flush;

  return 0;
}