统计

  • 随笔 - 50
  • 文章 - 42
  • 评论 - 147
  • 引用 - 0

留言簿(6)

随笔分类

文章分类

Link

搜索

  •  

积分与排名

  • 积分 - 154463
  • 排名 - 161

最新评论

阅读排行榜

评论排行榜

0-1背包问题
0-1背包问题是对空间问题,排布选择问题的抽象

所谓0-1标识的一个物体的两种状态,可以通俗的理解为一个物体是否放入背包内,放入为1,取出为0;

例如有题目有体积为1,2,3,4的四个物体,放入容积为5的背包,有几种方法?

又如输入两个整数m, n,要求找到所有小于n且和为m的所有组合?

都可简化为0-1背包问题,可归纳如下:
输入条件:
1-可累加对象的集合A{....}
2-对象的广义和sum
输出:
列出A的所有满足广义和为sum的子集

解决这类问题就是建立标记数组 BagArray
void bagProb(A,sum)
{
   foreach(elm in A)   //由大到小遍历集合A
   {
      if(elm<sum)
      {
         BagArray[index]=1;//放入背包
         batProb(A^b, sum-elm)
         BagArray[index]=0;//回溯
      }
      else if(elm==sum)
      {
         BagArray[index]=1;//放入背包
         printArray(BagArray);
         BagArray[index]=0;//回溯         
      }
   }
}
 以下是0-1背包其中一个问题的C++实现

 1#include "stdafx.h"
 2/************************************************************************/
 3/* 0-1背包问题 
 4输入两个整数m, n,要求找到所有小于n且和为m的所有组合  */

 5/************************************************************************/
 6int length=0;
 7void PrintBag(BYTE bag[])
 8{
 9    for(int i=1;i<=length;i++)
10    {
11        if(bag[i]==1)
12            cout<<i<<" ";
13    }

14    cout<<endl;
15}

16void BagProblem(int m,int n,BYTE bag[])
17{
18    if (n<1)
19        return;
20
21    if (n<m)
22    {
23        for (int i=n;i>0;i--)
24        {
25            bag[i]=1;
26            BagProblem(m-i,i-1,bag);
27            bag[i]=0;
28        }

29    }
 
30    else if(m==n)
31    {
32        bag[n]=1;
33        PrintBag(bag);
34        bag[n]=0;
35        BagProblem(m,n-1,bag);
36    }

37    else
38    {
39        BagProblem(m,m,bag);
40    }

41}

42void bag(int m,int n)
43{
44    if (n>m)
45    {
46        n=m;
47    }

48    BYTE *bag=new BYTE[n+1];
49    memset(bag,0,n+1);
50    length=n;
51    BagProblem(m,n,bag);
52    delete bag;
53}

posted on 2009-08-11 03:02 pear_li 阅读(2579) 评论(1)  编辑 收藏 引用 所属分类: C++

评论

# re: 0-1背包问题 2009-08-12 12:02 99读书人

好东西!!!
  回复  更多评论    

# re: 0-1背包问题 2009-08-13 10:12 Norz

不用递归...如何实现...
  回复  更多评论    

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理