博客

//集合nSrcArr 是否存在一个子集的和 等于 nDes

bool

IsExist

(const vector<int> &nSrcArr, int nDes)

{

vector<bool> nTemp1(nDes + 1, 0);

vector<bool> nTemp2(nDes + 1, 0);

nTemp1[0] = 1;

int nMin = 0;

int nSize = nSrcArr.size();

for (int i = 0; i < nSize; i++)

{

nMin = min(nDes, nSrcArr[i]);

for (int j = 0; j < nMin; j++)

{

nTemp2[j] = nTemp1[j];

}

for (int j = nMin; j < nDes + 1; j++)

{

nTemp2[j] = nTemp1[j] || nTemp1[ j – nSrcArr[i]];

}

nTemp1 = nTemp2;

}

return nTemp1[nDes];

}

//给定一个集合， 求出一个它的子集， 其和不超过W且尽量大

int

SubsetSum

(const vector<int> &nSrcArr, int nDes)

{

vector<int> nTemp1(nDes + 1, 0);

vector<int> nTemp2(nDes + 1, 0);

int nMin = 0;

int nSize = nSrcArr.size();

for (int i = 0; i < nSize; i++)

{

nMin = min(nSrcArr[i], nDes);

for (int j = 0; j < nMin; j++)

{

nTemp2[j] = nTemp1[j];

}

for (int j = nMin; j < nDes + 1; j++)

{

nTemp2[j] = max(nTemp1[j], nTemp1[j – nSrcArr[i]] + nSrcArr[i]);

}

nTemp1 = nTemp2;

}

return nTemp1[nDes];

}

//test

int main()

{

int nTest[] = { 30,70,60,90,20 };

int nSize = sizeof(nTest) / sizeof(nTest[0]);

vector<int> nArr(nTest, nTest + nSize);

bool bRes = IsExist(nArr, 120);

cout << bRes << endl;

int nRes = SubsetSum(nArr, 99);

cout << nRes << endl;

return 0;

}