佚名通过本文主要向大家介绍了自由组合定律题目,排列组合题目,排列组合经典题目,数学排列组合题目,排列组合典型题目等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
问题：组合数学题目的编程求解的效率问题
描述:
描述:
这么一道题：A={1,2,3,...,2015},B是A的一个子集，对B中任意三个元素x,y,z，都有x+y不等于z.
求B中元素最多时，集合B.
Card(B)的最大值是1008，Card(B)=1008时，B集合有且只有四个（应该很容易写出来：所有奇数集，{1008，……2015}，{1007，1009，……，2015}，{1007，……，2014}）
只有4个的证明还没想出来，想编程序找找反例。
用回溯法写了这个程序：算到N=101时，就悲剧了，更别提N=2015了。想想应该是2^N型的问题，大虾们有没有什么好办法？我自己感觉自己的回溯写得太烂了，有兴趣和时间的大虾能不能以此题写一个范例供我学习下。
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef vector<int> Set;
typedef vector<vector<int> > ResSet;
int getMinChoice(Set status, Set b)
{
unsigned int i,k;
k = b.size();
i = (k == 0)? 0 : b.back();
while (1){
if (i+1 > status.size())
break;
else if (status[i] == 0)
break;
i++;
}
return i;
}
int main()
{
int num, temp, tmpindex,flag=0;
unsigned int k;
Set w;
ResSet res;
Set b;
Set status;
Set reslen;
//freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
scanf("%d", &num);
for (int i = 0; i<num; i++){
w.push_back(i + 1);
status.push_back(0);
}
while (1)
{
temp = getMinChoice(status, b);
if (temp < num)
{
b.push_back(temp + 1);
flag = 1;
status[temp] = -1;
for (k = 0; k+1 < b.size(); k++)
{
tmpindex = b[k] + temp;
if (tmpindex < num)
status[tmpindex]++;
}
}
else
{
if (flag == 1)
{
if (b.size() == (num + 2) / 2)
{
res.push_back(b);
}
//reslen.push_back(b.size());
temp = b.back();
b.pop_back();
for (k = 0; k < b.size(); k++)
{
tmpindex = b[k] + temp - 1;
if (tmpindex < num)
status[tmpindex]--;
}
flag = 0;
}
else if (flag == 0)
{
if (b.size() == 0)
break;
temp = b.back();
b.pop_back();
for (k = 0; k < b.size(); k++)
{
tmpindex = b[k] + temp - 1;
if (tmpindex < num)
status[tmpindex]--;
}
for (k = temp; k < num; k++)
{
if (status[k] == -1)
status[k] = 0;
}
}
}
}
cout << res.size() << endl;
for (unsigned i = 0; i< res.size(); i++)
{
Set b = res[i];
for (unsigned j = 0; j<b.size(); j++)
{
cout << b[j] << ",";
}
cout << endl;
}
return 0;
}