01背包 求若干数的和为定值 【】代码有 求解释关键条件
本帖最后由 titer1 于 2012-08-09 15:38:22 编辑
//来源v_july_v博客
//输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,
//使其和等于 m ,要求将其中所有的可能组合列出来。
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
/**
* 输入t， r， 尝试Wk
*/
void sumofsub(int t, int k ,int r, int& M, bool& flag, bool* X)
{
X[k] = true; // 选第k个数
if (t + k == M) // 若找到一个和为M，则设置解向量的标志位，输出解
{
flag = true;
for (int i = 1; i <= k; ++i)
{
if (X[i] == 1)
{
printf("%d ", i);
}
}
printf("/n");
}
else
{ // 若第k+1个数满足条件，则递归左子树
if (t + k + (k+1) <= M)
{
sumofsub(t + k, k + 1, r - k, M, flag, X);
}
// 若不选第k个数，选第k+1个数满足条件，则递归右子树
if ((t + r - k >= M) && (t + (k+1) <= M))
{
X[k] = false;
sumofsub(t, k + 1, r - k, M, flag, X);
}
}
}
void search(int& N, int& M)
{
// 初始化解空间
bool* X = (bool*)malloc(sizeof(bool) * (N+1));
memset(X, false, sizeof(bool) * (N+1));
int sum = (N + 1) * N * 0.5f;
if (1 > M || sum < M) // 预先排除无解情况
{
printf("not found/n");
return;
}
bool f = false;
sumofsub(0, 1, sum, M, f, X);
if (!f)
{
printf("not found/n");
}
free(X);
}
int main()
{
int N, M;
printf("请输入整数N和M/n");
scanf("%d%d", &N, &M);
search(N, M);
return 0;
}
