• 寻找和为定值的多个数
    • 题目描述
    • 分析与解法
      • 解法一
      • 解法二
    • 0-1背包问题
    • 举一反三

    寻找和为定值的多个数

    题目描述

    输入两个整数n和sum，从数列1，2，3…….n 中随意取几个数，使其和等于sum，要求将其中所有的可能组合列出来。

    分析与解法

    解法一

    注意到取n，和不取n个区别即可，考虑是否取第n个数的策略，可以转化为一个只和前n-1个数相关的问题。

    • 如果取第n个数，那么问题就转化为“取前n-1个数使得它们的和为sum-n”，对应的代码语句就是sumOfkNumber(sum - n, n - 1)；
    • 如果不取第n个数，那么问题就转化为“取前n-1个数使得他们的和为sum”，对应的代码语句为sumOfkNumber(sum, n - 1)。

    参考代码如下：

    1. list<int>list1;
    2. void SumOfkNumber(int sum, int n)
    3. {
    4.     // 递归出口
    5.     if (n <= 0 || sum <= 0)
    6.         return;
    8.     // 输出找到的结果
    9.     if (sum == n)
    10.     {
    11.         // 反转list
    12.         list1.reverse();
    13.         for (list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)
    14.             cout << *iter << " + ";
    15.         cout << n << endl;
    16.         list1.reverse()//此处还需反转回来
    17.     }
    19.     list1.push_front(n);      //典型的01背包问题
    20.     SumOfkNumber(sum - n, n - 1);   //“放”n，前n-1个数“填满”sum-n
    21.     list1.pop_front();
    22.     SumOfkNumber(sum, n - 1);     //不“放”n，n-1个数“填满”sum
    23. }

    解法二

    这个问题属于子集和问题（也是背包问题）。本程序采用回溯法+剪枝，其中X数组是解向量，t=∑(1,..,k-1)Wi*Xi, r=∑(k,..,n)Wi，且

    • 若t+Wk+W(k+1)<=M,则Xk=true，递归左儿子(X1,X2,..,X(k-1),1)；否则剪枝；
    • 若t+r-Wk>=M && t+W(k+1)<=M,则置Xk=0，递归右儿子(X1,X2,..,X(k-1),0)；否则剪枝；

    本题中W数组就是(1,2,..,n),所以直接用k代替WK值。

    代码编写如下：

    1. //输入t， r， 尝试Wk
    2. void SumOfkNumber(int t, int k, int r, int& M, bool& flag, bool* X)
    3. {
    4.     X[k] = true;   // 选第k个数
    5.     if (t + k == M) // 若找到一个和为M，则设置解向量的标志位，输出解
    6.     {
    7.         flag = true;
    8.         for (int i = 1; i <= k; ++i)
    9.         {
    10.             if (X[i] == 1)
    11.             {
    12.                 printf("%d ", i);
    13.             }
    14.         }
    15.         printf("\n");
    16.     }
    17.     else
    18.     {   // 若第k+1个数满足条件，则递归左子树
    19.         if (t + k + (k + 1) <= M)
    20.         {
    21.             SumOfkNumber(t + k, k + 1, r - k, M, flag, X);
    22.         }
    23.         // 若不选第k个数，选第k+1个数满足条件，则递归右子树
    24.         if ((t + r - k >= M) && (t + (k + 1) <= M))
    25.         {
    26.             X[k] = false;
    27.             SumOfkNumber(t, k + 1, r - k, M, flag, X);
    28.         }
    29.     }
    30. }
    32. void search(int& N, int& M)
    33. {
    34.     // 初始化解空间
    35.     bool* X = (bool*)malloc(sizeof(bool)* (N + 1));
    36.     memset(X, false, sizeof(bool)* (N + 1));
    37.     int sum = (N + 1) * N * 0.5f;
    38.     if (1 > M || sum < M) // 预先排除无解情况
    39.     {
    40.         printf("not found\n");
    41.         return;
    42.     }
    43.     bool f = false;
    44.     SumOfkNumber(0, 1, sum, M, f, X);
    45.     if (!f)
    46.     {
    47.         printf("not found\n");
    48.     }
    49.     free(X);
    50. }

    0-1背包问题

    0-1背包问题是最基础的背包问题，其具体描述为：有N件物品和一个容量为V的背包。放入第i件物品耗费的费用是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

    简单分析下：这是最基础的背包问题，特点是每种物品仅有一件，可以选择放或不放。用子问题定义状态：即F[i, v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

    • F[i, v] = max{F[i-1, v], F[i-1, v-Ci ] + Wi}

    根据前面的分析，我们不难理解这个方程的意义：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只和前 i-1 件物品相关的问题。即：

    • 如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为 F[i-1, v ]；
    • 如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-Ci的背包中”，此时能获得的最大价值就是F[i-1, v-Ci]再加上通过放入第i件物品获得的价值Wi。

    伪代码如下：

    1. F[0,0...V] ← 0
    2. for i ← 1 to N
    3.     for v ← Ci to V
    4.         F[i, v] ← max{F[i-1, v], F[i-1, v-Ci] + Wi }

    这段代码的时间和空间复杂度均为 O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O(V)。感兴趣的读者可以继续思考或者参考网上一个不错的文档《背包问题九讲》。

    举一反三

    1、《挑战程序设计竞赛》的开篇有个类似的抽签问题，挺有意思，题目如下：

    将写有数字的n个纸片放入一个纸箱子中，然后你和你的朋友从纸箱子中抽取4张纸片，每次记下纸片上的数字后放回子箱子中，如果这4个数字的和是m，代表你赢，否则就是你的朋友赢。

    请编写一个程序，当纸片上所写的数字是k1，k2，k3，k4，..，kn时，是否存在抽取4次和为m的方案，如果存在，输出YES；否则，输出NO。

    限制条件：

    • 1 <= n <= 50
    • 1 <= m <= 10^8
    • 1 <= ki <= 10^8

    分析：最容易想到的方案是用4个for循环直接穷举所有方案，时间复杂度为O（N^4）,主体代码如下：

    1. //通过4重for循环枚举所有方案
    2. for (int a = 0; a < n, a++)
    3. {
    4.     for (int b = 0; b < n; b++)
    5.     {
    6.         for (int c = 0; c < n; c++)
    7.         {
    8.             for (int d = 0; d < n; d++)
    9.             {
    10.                 if (k[a] + k[b] + k[c] + k[d] == m)
    11.                 {
    12.                     f = true;
    13.                 }
    14.             }
    15.         }
    16.     }
    17. }

    但如果当n远大于50时，则程序会显得非常吃力，如此，我们需要找到更好的办法。

    提供两个思路：

    ①最内侧关于d的循环所做的事情：检查是否有d满足ka+ kb +kc + kd = m，移动下式子，等价于：检查是否有d使得kd = m - ka - kb - kc，也就是说，只要检查k中所有元素，判断是否有等于m-ka-kb-ka 的元素即可。设m-ka-kb-ka = x，接下来，就是要看x是否存在于数组k中，此时，可以先把数组k排序，然后利用二分查找在数组k中找x；

    ②进一步，内侧的两个循环所做的事情：检查是否有c和d满足kc + kd = m - ka -kb。同样，可以预先枚举出kc+kd所得的n^2数字并排好序，便可以利用二分搜索继续求解。

    2、给定整数a1、a2、a3、…、an，判断是否可以从中选出若干个数，使得它们的和等于k（k任意给定，且满足-10^8 <= k <= 10^8）。

    分析：此题相对于本节“寻找满足条件的多个数”如出一辙，不同的是此题只要求判断，不要求把所有可能的组合给输出来。因为此题需要考虑到加上a[i]和不加上a[i]的情况，故可以采用深度优先搜索的办法，递归解决。

    3、有n个数，输出期中所有和为s的k个数的组合。

    分析：此题有两个坑，一是这里的n个数是任意给定的，不一定是：1,2,3…n，所以可能有重复的数（如果有重复的数怎么处理？）；二是不要求你输出所有和为s的全部组合，而只要求输出和为s的k个数的组合。

    举个例子，假定n=6，这6个数为：1 2 1 3 0 1，如果要求输出和为3的全部组合的话，

    • 1 2
    • 1 2 0
    • 0 3
    • 1 1 1
    • 1 1 1 0

    而题目加了个限制条件，若令k=2，则只要求输出：[{1,2}, {0,3}] 即可。