回溯算法求解01背包问题_利用回溯法编程求解0-1背包问题

问题描述

01背包问题是算法中的经典问题：
      对于给定的N个物品，第i个物品的重量为wi，价值为vi，对于一个最多能装重量c的背包，应该如何选择放入包中的物品，使得包中物品的总价值最大？

算法分析

简单来说回溯算法=深度优先遍历+剪枝，下面我们进行分析：

01背包属于最优解问题。对于每一个物品i，我们可以选择装入背包或不装入背包。对n个物品，我们顺序依次考虑每个物品，这样就形成了一棵二叉树。基本思想就是深度优先遍历这棵树，在搜索空间树时，左子节点是可一个可行结点，搜索就进入其左子树;对于右子树时，先计算上界函数，以判断是否将其减去（剪枝）。最后保存价值最大的情况，该方案就是最终结果。

时间复杂度：O(2^n)。

代码实现

code 1

#include <stdio.h>
 
int n;               // 物品数量
double c;            // 背包容量
double w[100];       // 各个物品的重量  weight
double v[100];       // 各个物品的价值  value
double cw = 0;       // 当前背包重量  current weight
double cv = 0;       // 当前背包中物品总价值  current value
double bestv = 0;    // 当前最优价值  best value
double perv[100];    // 单位物品价值(排序后)  per value
int cput[100];       // 当前物品放入情况
int put[100];        // 设置是否装入，为1的时候表示选择该组数据装入，为0的表示不选择该组数据
int i, j;            // 循环使用
 
// 计算上界
double bound(int index) {
    int rp = 0;
    // 计算剩余物品重量和
    while(index <= n) { 
        rp += v[index];
        index++;
    }
    return cv + rp;
}
 
// 回溯法
void backtrack(int index) {
    // 如果已经处理完所有物品
    if (index > n) {
        // 记录装入情况
        for(i = 1; i <=n; i++) {
            put[i] = cput[i];
        }
        // 更新当前最优价值
        bestv = cv;
        return;
    }
 
    if (cw + w[index] <= c) {
        cw += w[index];
        cv += v[index];
        cput[index] = 1;
        backtrack(index + 1);
        // 回溯
        cw -= w[index];
        cv -= v[index];
    }
 
    // 如果剩余物品的上界价值大于当前最优价值，尝试不放入
    if (bound(index + 1) > bestv) {
        cput[index] = 0;
        backtrack(index + 1);
    }
}
 
// 01背包问题
void knapsack() {
    printf("请输入物品的数量和背包的容量：\n");
    scanf("%d %lf", &n, &c);
 
    printf("请输入每个物品的重量：\n");
    for (i = 1; i <= n; i++) {
        scanf("%lf", &w[i]);
    }
 
    printf("请输入每个物品的价值：\n");
    for (i = 1; i <= n; i++) {
        scanf("%lf", &v[i]);
    }
    backtrack(1);
    printf("最优价值为：\n%.0lf\n", bestv);
    printf("最佳选择为：\n");
    for (i = 1; i <= n; i++) {
        // printf("%d", put[i]);
        if(put[i] == 1) {
            printf("1\n");
        } else {
            printf("0\n");
        }
    }
}
 
int main() {
    knapsack();
}

code2 

以下是贪心策略优化后的代码实现

#include <stdio.h>
 
int n;               // 物品数量
double c;            // 背包容量
double w[100];       // 各个物品的重量  weight
double v[100];       // 各个物品的价值  value
double cw = 0;       // 当前背包重量  current weight
double cv = 0;       // 当前背包中物品总价值  current value
double bestv = 0;    // 当前最优价值  best value
double perv[100];    // 单位物品价值(排序后)  per value
int cput[100];       // 当前物品放入情况
int put[100];        // 设置是否装入，为1的时候表示选择该组数据装入，为0的表示不选择该组数据
int order[100];      // 物品的编号
int i, j;            // 循环使用
 
// 对输入数据进行排序处理
void initsort() {
    for(i = 1; i <= n; i++)
        order[i] = i;
    int temporder = 0;
    double temp = 0.0;
    // 计算单位价值（单位重量的物品价值）
    for(i = 1; i <= n; i++)
        perv[i] = v[i] / w[i]; 
    for(i = 1; i <= n - 1; i++) {
        for(j = i + 1; j <= n; j++) {
            if(perv[i] < perv[j]) { 
                // 对单位价值进行排序，同时对对应其他数据排序
                temp = perv[i];
                perv[i] = perv[j];
                perv[j] = temp;
 
                temporder = order[i];
                order[i] = order[j];
                order[j] = temporder;
 
                temp = v[i];
                v[i] = v[j];
                v[j] = temp;
  
                temp = w[i];
                w[i] = w[j];
                w[j] = temp;
            }
        }
    }
}
 
// 计算上界
double bound(int index) {   
    // 判断当前背包的总价值cv＋剩余容量可容纳的最大价值<=当前最优价值
    double leftw = c - cw; // 剩余背包容量
    double b = cv; // 记录当前背包的总价值cv，最后求上界
    // 以物品单位重量价值递减次序装入物品
    while(index <= n && w[index] <= leftw) {
        leftw -= w[index];
        b += v[index];
        index++;
    }
    //装满背包
    if(index <= n)
        b += v[index] / w[index] * leftw;
    return b;
}
 
// 回溯法
void backtrack(int index) {
    // 如果已经处理完所有物品
    if (index > n) {
        // 记录装入情况
        for(i = 1; i <=n; i++) {
            put[i] = cput[i];
        }
        // 更新当前最优价值
        bestv = cv;
        return;
    }
 
    if (cw + w[index] <= c) {
        cw += w[index];
        cv += v[index];
        cput[index] = 1;
        backtrack(index + 1);
        // 回溯
        cw -= w[index];
        cv -= v[index];
    }
 
    // 如果剩余物品的上界价值大于当前最优价值，尝试不放入
    if (bound(index + 1) > bestv) {
        cput[index] = 0;
        backtrack(index + 1);
    }
}
 
// 恢复排序
void endsort() {
    int temput = 0;
    int temporder = 0;
    for(i = 1; i <= n - 1; i++) {
        for(j = i + 1; j <= n; j++) {
            if(order[i] > order[j]) {
                temporder = order[i];
                order[i] = order[j];
                order[j] = temporder;
 
                temput = put[i];
                put[i] = put[j];
                put[j] = temput; 
            }
        }
    }
}
 
// 01背包问题
void knapsack() {
    printf("请输入物品的数量和背包的容量：\n");
    scanf("%d %lf", &n, &c);
 
    printf("请输入每个物品的重量：\n");
    for (i = 1; i <= n; i++) {
        scanf("%lf", &w[i]);
    }
 
    printf("请输入每个物品的价值：\n");
    for (i = 1; i <= n; i++) {
        scanf("%lf", &v[i]);
    }
 
    initsort();
    backtrack(1);
    endsort();
 
    printf("最优价值为：\n%.0lf\n", bestv);
    printf("最佳选择为：\n");
    for (i = 1; i <= n; i++) {
        // printf("%d", put[i]);
        if(put[i] == 1) {
            printf("1\n");
        } else {
            printf("0\n");
        }
    }
}
 
int main() {
    knapsack();
}

样例测试

输入

10 165
23 31 29 44 53 38 63 85 89 82
92 57 49 68 60 43 67 84 87 72

15 750
70 73 77 80 82 87 90 94 98 106 110 113 115 118 120
135 139 149 150 156 163 173 184 192 201 210 214 221 229 240

输出 

最优价值为：
309
最佳选择为：
1
1
1
1
0
1
0
0
0
0

最优价值为：
1458
最佳选择为：
1
0
1
0
1
0
1
1
1
0
0
0
0
1
1

算法分析

适用性

当需要找出某个问题的解集（全部解）或者要求回答什么解是满足某些约束条件的最优解时，往往要使用回溯法。

注意事项

回溯法涉及到深度优先搜索，递归，以及状态空间树的遍历。需要理解如何构建状态空间树、如何选择分支、如何递归地搜索解空间等，需要对问题进行合理分析及解空间树的抽象化。同时剪枝策略是一项重要的技巧，它可以帮助减小搜索空间，从而提高算法的效率，剪枝的实现也具有一定的难度。

效率

回溯法是一种穷举法，它会遍历所有可能的情况放入组合。因此，其时间复杂度是指数级别的，为O(2^n)。01背包问题中，剩余物品价值上界剪枝和容量剪枝是两个常用的策略，它们可以显著减少搜索的复杂性，提高算法效率。

总结

回溯算法

回溯是一种搜索算法，用于解决组合优化问题。它尝试在问题的解空间中搜索不同的组合，以找到最优解。回溯算法的核心思想是深度优先搜索，递归地探索解空间树的各个分支，同时使用剪枝策略来减少搜索空间，提高效率。

回溯过程

回溯算法的核心是 backtrack 函数，该函数递归地探索解空间，考虑以下情况：

如果已经处理完所有物品，记录当前最优解（装入情况）和更新最优价值。

如果当前物品的重量可以放入背包，选择装入该物品，更新当前背包的重量和总价值，继续处理下一个物品。

如果剩余物品的上界价值仍然大于当前最优价值，尝试不放入当前物品，继续搜索。

上界剪枝

为了提高效率，算法使用上界函数 bound 来估计剩余未处理物品的最大可能总价值。如果该上界小于当前最优解，就不再继续搜索该分支，从而减少搜索空间。

[回溯法是按照深度优先的方式对解空间树（状态空间树）进行搜索，从而求得最优解的算法。可以使用贪心算法对该方法进行优化（见Code2），同时更改剪枝策略，可以更加有效的提高算法的效率。]