Chinaunix首页 | 论坛 | 博客
  • 博客访问: 143932
  • 博文数量: 35
  • 博客积分: 2386
  • 博客等级: 大尉
  • 技术积分: 380
  • 用 户 组: 普通用户
  • 注册时间: 2009-05-05 06:11
文章分类

全部博文(35)

文章存档

2011年(1)

2010年(2)

2009年(32)

分类:

2009-05-09 16:25:43

输入两个整数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]

阅读(1102) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~