背包问题

一、原理
        背包问题：设有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的方案，使选择物品的总重量不超过指定的限制重量，但选择物品的价值之和为最大。
        设n件物品的重量分别为w₀，w₁，...，w_n-1，物品的价值分别为v₀， v₁，...，v_n-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