Задача о сумме подмножеств

...или subset sum problem по-ихнему, подробно описана в Вики. Ниже в консольном приложении Visual Studio 2015 мы решаем её с помощью рекурсии на тесте из Вики. Наше решение оказывается совсем простым, временная сложность алгоритма не оценивалась :)

//Visual Studio 2015
#include <iostream>
using namespace std;

int items[] = { -7, -3, -2, 5, 8 }; //Исходное множество
int n = sizeof(items) / sizeof(int); //Размер
int *set; //Искомое подмножество

void subsum(int i, int weight) { //Поиск и вывод элементов
 int j;
 if (i && !weight) {
  for (j = 0; j < i; j++) {
   int item = items[set[j]];
   cout << (j ? " " : "") << items[set[j]];
  }
  cout << endl;
 }
 for (j = i ? set[i - 1] + 1 : 0; j < n; j++) {
  set[i] = j;
  subsum(i + 1, weight + items[j]);
 }
}

int main() {
 set = new int[n];

 subsum(0, 0);

 delete set;
 cin.get();
 return 0;
}

Если хотим решить за (псевдо)полиномиальное время, платой за этой будет необходимость составлять дополнительные таблицы, вот подход к решению (не выводит подмножество, а только определяет, существует ли оно для некоторой суммы sum).

//Visual Studio 2015
#include <iostream>
using namespace std;

bool isSubsetSum (int set[], int n, int sum) {
 bool **subset;
 subset = new bool * [n+1];
 for (int i=0; i<n+1; i++) subset[i] = new bool [sum + 1];

 for (int i = 0; i <= n; i++) subset[i][0] = true;
 for (int i = 1; i <= sum; i++) subset[0][i] = false;

 //Заполнить таблицу подмножеств для поиска ответа
 for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= sum; j++) {
   if (j<set[i - 1]) subset[i][j] = subset[i - 1][j];
   if (j >= set[i - 1])    
    subset[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]];
  }
 }

 //Блок для печати таблицы
 for (int i = 0; i <= n; i++) {
  for (int j = 0; j <= sum; j++) {
   cout.width (4); cout << subset[i][j];
  }
  cout << endl;
 }

 bool val = subset[n][sum];
 for (int i = n; i>-1; i--) delete[] subset[i];
 delete subset;
 return val;
}

int main() {
 int set[] = { -7, -3, -2, 5, 8 }; //Исходное множество
 int n = sizeof(set) / sizeof(set[0]); //Размер
 int sum = 0; //Сумма
 if (isSubsetSum(set, n, sum)) cout << "Yes";
 else cout << "No";
 
 cin.get();
 return 0;
}

27.05.2018, 12:34 [3249 просмотров]