0-1背包问题

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

解析

    这是一道0-1背包问题。0-1背包问题是这样的：设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w[1],w[2],...,w[n]。问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解，否则称背包问题无解。试用递归方法设计求解背包问题的算法

/*
 * 0-1 knapsack problem
 *     This code snippet provides a recursive method to solve the 0-1 knapsack problem
 *
 * @author: openspace
 * @date: 2009-05-09
 */
 
 bool knmp(int m, int n)
 {
      if (m == 0)
          return true;
      else if (m < 0 || (m > 0 && n < 1)
          return false;
      else
          return knmp(m, n - 1) || knmp(m - n, n - 1)
 }

0-1背包问题定义

KNMP(s, n) =
    1) True              s = 0             此时背包问题一定有解
    2) False             s < 0             总重量不能为负数
    3) False             s > 0 且 n < 1    物品件数不能为负数
    4) KNMP(s, n-1)或者  s > 0 且 n >=1    所选物品中不包含w[n]时
       KNMP(s-w[n], n-1)                   所选物品中包括w[n]时