背包问题-贪心算法求解

2022/4/23 9:12:44

本文主要是介绍背包问题-贪心算法求解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述:

给定n种物品和一个背包。物品i的重量是wi,其价值为pi,背包的容量为M。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?

读题可获得的信息

  1. 物品数量:n
  2. 背包容量:m
  3. 物品的价值:pi
  4. 物品的重量:wi

思路分析:

如果要使装入的背包中的物品总价值最大,那么就需要同时考虑,物品的价值和重量,这里我们用pi/wi得到一个比值(这里使用),如果这个比值越大那么装入背包的收益就会越大

快排算法设计:

把每一个物品的价值比(pi/wi),存入到一个数组中,并且按照从大到小的顺序进行排序

这里我们使用快速排序的单边循环法,进行排序

  • 快排单边循环的主要思想:
    • 选定基准元素P,同时设置一个M指针代表小于基准元素的区域边界
    • 从左到右遍历
      • 如果遍历到的元素 比基准元素P要大,那么就继续遍历
      • 如果遍历到的元素比基准元素P要下,那么M指针向右移动,并且将遍历到的元素和M指针所在的元素交换位置
    • 当遍历结束时,让基准元素PM指向的元素交换即可

时间复杂度:O(nlogn)

空间复杂度:O(1),使用了交换法,不需要开辟额外的空间

package shiyan4;

/**
 * @author DL5O
 * @version 1.0
 */
public class Utils {
    public static void quickSort(Good[] array, int startIndex, int endIndex) {
        //递归退出标志
        if (startIndex >= endIndex) {
            return;
        }
        //单边循环法
        int pivotIndex = partition(array, startIndex, endIndex);
        quickSort(array, startIndex, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, endIndex);
    }

    public static int partition(Good[] array, int startIndex, int endIndex) {
        //选取第1个元素为基准元素
        Good pivot = array[startIndex];
        //小于基准元素的区域边界
        int mark = startIndex;
        //按照从大到小进行排序
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (array[i].values > pivot.values) {
                //该元素比基准元素大,需要放入区域,所以区域增大1
                mark++;
                //放入区域
                Good temp = array[mark];
                array[mark] = array[i];
                array[i] = temp;
            }
        }
        //将基准元素交换到区域边界位置
        array[startIndex] = array[mark];
        array[mark] = pivot;
        return mark;
    }

    public static void outputGoods(Good goods[]){
        for (Good good:
                goods) {
            System.out.println(good);
        }
    }
}

用例:

物品 重量(kg) 价格(元) 单位重量的价值(/kg)
A 30 60 2
B 20 40 2
C 20 30 2/3
D 10 10 1
package shiyan4;

/**
 * @author DL5O
 * @version 1.0
 */ //物品类
public class Good {
    public String name;
    public double weight;
    public double price;
    public double values;

    public Good(String name, double weight, double price) {
        this.name = name;
        this.weight = weight;
        this.price = price;
        this.values = price / weight;
    }

    @Override
    public String toString() {
        return "商品{" +
                "名称:'" + name + '\'' +
                ",总量: " + weight +
                ", 价格:" + price +
                ", 价值:" + values +
                '}';
    }
}


  • 将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品,单位重量的价值排序:物品A > 物品B > 物品C

  • 总是优先选择单位重量下价值最大的物品,单位重量的价值排序:物品A > 物品B > 物品C

贪心算法设计:

/**
* 利用贪心算法获取能够让 背包中选着的商品的价值最大的排列祝贺
* @param goods 商品列表(无序的)
* @return 商品的排列组合
*/
public  ArrayList<Good> getMaxValue(Good[] goods)
  1. 先对goods,商品数组进行排序,这里我使用的是快速排序,上面有介绍
  2. ArrayList<Good> ret:ret集合用于记录被选择的商品序列
  3. curWeight:当前背包容量,初始化为maxWeight
  4. n:物品的件数
  5. 进行选择,从第一件物品开始选
    • 如果当前商品的重量量 大于 当前背包容量 退出则退出循环
    • 如果不大于就把物品装入,直到背包装不下该物品
  6. 内层循环
    • 装当前价值最大的物品,直到装不下位置,每次装完物品之后,让当前背包容量减去物品的容量
    • 如果 goods[i].weight > curWeight 那么就开始装下一个物品
package shiyan4;

import java.util.ArrayList;

/**
 * @author DL5O
 * @version 1.0
 */
public class Bag {
    public double maxWeight = 0;//背包的总容量

    public Bag(double maxWeight) {
        this.maxWeight = maxWeight;
    }

    /**
     * 利用贪心算法获取能够让 背包中选着的商品的价值最大的排列祝贺
     * @param goods 商品列表(无序的)
     * @return 商品的排列组合
     */
    public  ArrayList<Good> getMaxValue(Good[] goods){
        Utils.quickSort(goods,0,goods.length-1);//对goods数组进行快速排序
        ArrayList<Good> ret= new ArrayList<>();
        double sumValues = 0;//总价值
        double curWeight = maxWeight;//当前背包容量,
        int n = goods.length;//物品的件数
        //进行选择,从第一件物品开始选
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {//进行判断是否还有其他物品可以装,装不下就退出循环
                if(goods[i].weight > curWeight){//如果当前商品的总量 大于 当前背包容量 退出则退出循环
                    break;
                }else{
                    //装当前价值最大的物品,直到装不下位置,每次装完物品之后,让当前背包容量减去物品的容量
                    //如果 goods[i].weight > curWeight 那么就开始装下一个物品
                    while(true){
                        curWeight -= goods[i].weight;//让当前背包容量减去物品的容量
                        System.out.print("选择物品 " + goods[i].name);
                        System.out.println(",当前剩余容量 " + curWeight);
                        sumValues +=goods[i].price;//把当前决策玩之后的物品的价格进行累加,并保存
                        ret.add(goods[i]);
                        if(goods[i].weight > curWeight){
                            System.out.println( goods[i].name+" 装不下了");
                            break;
                        }
                    }
                }
            }
        }
        System.out.println("最大价值为:" + sumValues );
        return ret;//解向量
    }

    public double getMaxWeight() {
        return maxWeight;
    }

    public void setMaxWeight(double maxWeight) {
        this.maxWeight = maxWeight;
    }
}

测试类

package shiyan4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

/**
 * @author DL5O
 * @version 1.0
 */
public class Shiyan4 {
    public static void main(String[] args) {

        //创建商品对象
        Good a=new Good("A",30,60);
        Good b=new Good("B",20,40);
        Good c=new Good("C",20,30);
        //装入good对象数组中
        Good[] goods = {a,c,b};

        //初始化背包最大总容量
        Bag bag = new Bag(50);
        //获取最大值
        ArrayList<Good> ret = bag.getMaxValue(goods);

        System.out.println("====解向量====");
        for (Good good : ret) {
            System.out.println(good);
        }
    }
}


这篇关于背包问题-贪心算法求解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程