Chinaunix首页 | 论坛 | 博客
  • 博客访问: 460939
  • 博文数量: 285
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 629
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-14 17:53
个人简介

相信自己,快乐每一天

文章分类

全部博文(285)

分类: 架构设计与优化

2013-11-01 15:04:35

原文地址:背包问题 作者:scq2099yt

一、原理
        背包问题:设有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的方案,使选择物品的总重量不超过指定的限制重量,但选择物品的价值之和为最大。
        设n件物品的重量分别为w0,w1,...,wn-1,物品的价值分别为v0, v1,...,vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值设为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成毫无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会再被考察。这同时保证函数后找到的方案一定会比前面的方案更好。

二、算法
        算法中,第i件物品的选择有两种可能:
        (1)物品i被选择,这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后,继续递归去考虑其余物品的选择;
        (2)物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。
        按以上思想写出递归算法如下(用伪码表示):
        find (物品i,当前选择已达到的重量和tw,本方案可能达到的总价值为tv)
        {
            // 考虑物品i包含在当前方案中的可能性
            if (包含物品i是可接受的)
            {
                // 将物品i包含当前方案中
                if (i < n-1)
                {
                    find(i+1, tw+物品i的重量, tv);
                }
                else
                {
                    // 又一个完整方案,因它比前面的方案好,以它作为最佳方案
                    以当前方案作为临时最佳方案保存;
                }
                恢复物品i不包含状态;
            }
            // 考虑物品i不包含在当前方案中的可能性
            if (不包含物品i仅是可考虑的)
            {
                if (i < n-1)
                {
                    find(i+1, tw, tv-物品i的价值);
                }
                else
                {
                    // 又一个完整方案,因它比前面的方案好,以它作为最佳方案
                    以当前方案作为临时最佳方案保存;
                }
            }
        }

三、程序
        按照前述算法编写背包问题代码如下:
        #include
        #define N 100
        int limitw,
        totv,            // 限制的总重量
        maxv;           // 全部物品的总价
        int option[N], cop[N];
        struct
        {
            int weight;
            int value;
        }a[N];
        int n;            // 物品种数次
        void find(int i, int tw, int tv)
        {
            int k;
            if (tw+a[i].weight <= limitw)
            {
                cop[i] = 1;
                if (i < n-1)
                {
                    find(i+1, tw+a[i].weight, tv);
                }
                else
                {
                    for (k=0; k                     {
                        option[k] = cop[k];
                    }
                    maxv = tv;
                }
                cop[i] = 0;
            }
            if (tv - a[i].value > maxv)
            {
                if (i < n-1)
                {
                    find(i+1, tw, tv-a[i].value);
                }
                else
                {
                    for (k=0; k                     {
                        option[k] = cop[k];
                    }
                    maxv = tv - a[i].value;
                }
            }
        }
        int main()
        {
            int k, w, v;
            printf("物品种数: ");
            scanf("%d", &n);
            for (totv=0,k=0; k             {
                printf(" 第%d种物品(重量, 价值): ", k+1);
                scanf("%d, %d", &w, &v);
                a[k].weight = w;
                a[k].value = v;
                totv += v;
            }
            printf("背包所能承受的总重量: ");
            scanf("%d", &limitw);
            maxv = 0;
            for (k=0; k             {
                cop[k] = 0;
            }
            find(0, 0, totv);
            printf("最佳装填方案是: \n");
            for (k=0; k             {
                if (option[k])
                {
                    printf(" 第%d种物品\n", k+1);
                }
            }
            printf(" 总价值=%d\n", maxv);
            return 0;
        }       
        本程序的一次执行结果如下:
        物品种数:
              第1种物品(重量,价值):3, 10
              第2种物品(重量,价值):5, 8
              第3种物品(重量,价值):2, 7
              第4种物品(重量,价值):8, 20
              第5种物品(重量,价值):6, 5
        背包所能承受的总重量:16
        最佳装填方案是:
              第1种物品
              第2种物品
              第4种物品
        总价值=38




阅读(373) | 评论(0) | 转发(0) |
0

上一篇:排序之直接插入排序

下一篇:哈希表查找

给主人留下些什么吧!~~