0-1背包问题—回溯算法—java实现

╰半夏微凉° 2022-04-13 05:42 169阅读 0赞

## 0-1背包问题 ##

## 【问题描述】 ##

有n种可选物品1，…，n ，放入容量为c的背包内，使装入的物品具有最大效益。
    表示
    n ：物品个数
    c ：背包容量
    p1,p2, …, pn：个体物品效益值
    w1,w2, …，wn：个体物品容量

## 【问题解析】 ##

0-1背包问题的解指：物品1,…,n的一种放法(x1, ···,xn的0/1赋值)，使得效益值最大。
    假定背包容量不足以装入所有物品：面临选择
    【优化原理】无论优化解是否放物品1，优化解对物品2,…,n的放法，相对剩余背包容量，也是优化解。
    
    首先给出所需要的变量：
    ```
    private static int[] p;//物品的价值数组
    private static int[] w;//物品的重量数组
    private static int c;//最大可以拿的重量
    private static int count;//物品的个数
    
    private static int cw;//当前的重量
    private static int cp;//当前的价值
    static int bestp;//目前最优装载的价值
    private static int r;//剩余物品的价值
    
    private static int[] cx;//存放当前解
    private static int[] bestx;//存放最终解
    ```
    解空间树：子集树
    可行性约束条件：cw + w[t] < c
    上界函数：cp + r <= bestp，即如果当前结点满足这个条件时，就可以将该结点的右子树剪去。

## \[核心算法\] ##

```
    /**
     * 回溯
     * @param t
     */
    public static void BackTrack(int t) {
        if(t>count) {//到达叶结点
            if(cp>bestp) {
                for(int i = 1;i<=count;i++) {
                    bestx[i] = cx[i];
                }
    
                bestp = cp;
            }
            return;
        }
    
        r -= p[t];
        if(cw + w[t] <= c) {//搜索左子树
            cx[t] = 1;
            cp += p[t];
            cw += w[t];
            BackTrack(t+1);
            cp -= p[t];//恢复现场
            cw -= w[t];//恢复现场
    
        }
    
        if(cp + r >bestp) {//剪枝操作
            cx[t] = 0;//搜索右子树
            BackTrack(t+1);
        }
        r += p[t];//恢复现场
    }
    
    ```

## \[完整代码\] ##

```
    package sort;
    
    public class Zero_One {
    private static int[] p;//物品的价值数组
    private static int[] w;//物品的重量数组
    private static int c;//最大可以拿的重量
    private static int count;//物品的个数
    
    private static int cw;//当前的重量
    private static int cp;//当前的价值
    static int bestp;//目前最优装载的价值
    private static int r;//剩余物品的价值
    
    private static int[] cx;//存放当前解
    private static int[] bestx;//存放最终解
    
    public static int Loading(int[] ww,int[] pp, int cc) {
        //初始化数据成员，数组下标从1开始
        count = ww.length - 1;
        w = ww;
        p = pp;
        c = cc;
        cw = 0;
        bestp = 0;
        cx = new int[count+1];
        bestx = new int [count+1];
    
        //初始化r，即剩余最大价格
        for(int i = 1;i<=count;i++) {
            r += p[i];
        }
    
        //调用回溯法计算
        BackTrack(1);
        return bestp;   
    }
    
    /**
     * 回溯
     * @param t
     */
    public static void BackTrack(int t) {
        if(t>count) {//到达叶结点
            if(cp>bestp) {
                for(int i = 1;i<=count;i++) {
                    bestx[i] = cx[i];
                }
    
                bestp = cp;
            }
            return;
        }
    
        r -= p[t];
        if(cw + w[t] <= c) {//搜索左子树
            cx[t] = 1;
            cp += p[t];
            cw += w[t];
            BackTrack(t+1);
            cp -= p[t];//恢复现场
            cw -= w[t];//恢复现场
    
        }
    
        if(cp + r >bestp) {//剪枝操作
            cx[t] = 0;//搜索右子树
            BackTrack(t+1);
        }
        r += p[t];//恢复现场
    }
    
    
    
    public static void main(String[] args) {
        //测试
        int[] w1 = {0,15,25,40,20,15,24};
        int[] p1 = {0,10,5,20,2,14,23};
        int c1 = 30;
        Loading(w1,p1,c1);
        System.out.println("最优装载为：" + bestp);
        for(int i =1;i<=count;i++) {
            System.out.print(bestx[i] + " ");
        }           
    }

## \[运行示例\] ##

![运行][70]

[70]: /images/20220413/096c317a60744efaa9776dc816d791fd.png