回溯法:0-1背包问题

发布时间:2024年01月20日

问题描述

给定n种物品和一背包。 物品i的重量是w_i, 其价值为v_i,背包的容量为 c。 问应该如何选择装入背包中的物品,使得装入背包中物品的总价值最大?注意物品不重复!

实例:物品价值V={12, 11, 9, 8}, 物品重量W={8, 6, 4, 3}, 背包容量c=13

结点:向量(x_1,x_2,...,x_k) ( 子集的部分特征向量)

搜索空间: 子集树2^n片树叶

其中两个可行解为:

<0,1,1,1>:x_1=0,x_2=1,x_3=1,x_4=1\\ <1,0,1,0>:x_1=1,x_2=0,x_3=1,x_4=0

回溯法模版回顾?

参考文章:代码随想录

回溯法解决的问题都可以抽象为树形结构,是的,我指的是所有回溯法的问题都可以抽象为树形结构!

因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度

递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

实现代码

终止条件代码

public static void backtracking(int n,  int startIndex) {
    if (startIndex>=n){
        //此时startIndex越界了
        if (getPathSum()<=c){
            result.add(new ArrayList<>(path));
            return;
        }
        return;
    }
    //再加后面任意一个就肯定不够了
    if (getPathSum()<=c&&(getPathSum() + items_min_weight[startIndex]) > c) {
        //        if (getPathSum()<c) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = startIndex; i < n; i++) {
        path.add(i);
        backtracking(n,  i + 1);
        path.removeLast();
    }

最终代码(含注释)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class KnapsackProblem {
    static List<List<Integer>> result = new ArrayList<>();
    static LinkedList<Integer> path = new LinkedList<>();

    static int N = 4;
    //    static int[] items_weight = new int[N];
    static int[] items_weight = {8, 6, 4, 3};
    //    static int[] items_value = new int[N];
    static int[] items_value = {12, 11, 9, 8};
    //每个items_min_weight(对应下标为i)的值为min{items_weight[i],...,items_weight[N-1]}
    static int[] items_min_weight = new int[N];
    //c为背包的容量
    static int c=13;

    public static void main(String[] args) {
        items_min_weight[N - 1] = items_weight[N - 1];
        int min = items_min_weight[N - 1];
        for (int i = items_weight.length - 2; i >= 0; i--) {
            if (items_weight[i] < min) {
                min = items_weight[i];
            }
            items_min_weight[i] = min;
        }
        backtracking(N,  0);
        System.out.println("可行解有:");
        result.forEach(System.out::println);
        //要是想求最优解,直接对每个可行解对应重量求和,之后取最大一个就好啦
    }

    public static void backtracking(int n,  int startIndex) {
        if (startIndex>=n){
            //此时startIndex越界了
            if (getPathSum()<=c){
                result.add(new ArrayList<>(path));
                return;
            }
            return;
        }
        //再加后面任意一个就肯定不够了
        if (getPathSum()<=c&&(getPathSum() + items_min_weight[startIndex]) > c) {
            //        if (getPathSum()<c) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < n; i++) {
            path.add(i);
            backtracking(n,  i + 1);
            path.removeLast();
        }
    }

    public static int getPathSum() {
        int sum = 0;
        for (int i = 0; i < path.size(); i++) {
            sum += items_weight[path.get(i)];
        }
        return sum;
    }
}
文章来源:https://blog.csdn.net/weixin_50917576/article/details/135708087
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。