原创

【回溯算法】之 0-1背包问题 -- Java实现


基本的0-1背包问题:

给定一些物品,每个物品的重量不相同且每个物体不可分割。在满足背包所能承受的最大重量的前提下,求改背包最大能够装载多少重量的物品。

例如,给定5个物品,每个物品的重量分别为 2,2,4,6,3,背包最大承受重量为9,求该背包最大能够装载的物品重量为多大。


回溯算法思想:

每一个物品都对应着两种状态,装,不装。通过穷举所有的状态,找到满足背包最大重量的值。


代码实现:

/**
     * 
     * @param i   当前的物品
     * @param n   物品总数
     * @param cw  背包当前重量
     * @param w   背包最大承受重量
     * @param weights  每个物品重量
     */

 

    int maxCw = Integer.MIN_VALUE;     //声明一个全局变量存放最大重量值


    public void putPackage_1(int i,int n,int cw,int w,int[] weights){
        if(i == n || cw == w) {  //i==n表示 处理完所有物体,cw==w表示装满了
            if(cw > maxCw) {
                maxCw = cw;
            }
            return;
        }
        
        putPackage_1(i+1, n, cw, w);   //不放入当前物品
        if(cw + weights[i] <= w) {
            putPackage_1(i+1, n, cw+weights[i], w);  //放入当前物品
        }
        
    }

 

 

调用形式:  weights = {2,2,4,6,3};   putPackage_1(0, 5, 0, 10,weights);   //代表当前处理第0个物品,总的物品数为5,当前背包重量为0,背包最大重量为10,每个物品的重量通过weights来表示

 

Java