背包问题求解

求解代码

package com.pan.test.domain;


import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.lang3.builder.EqualsBuilder;
import org.apache.commons.lang3.builder.HashCodeBuilder;
import org.assertj.core.util.Lists;

import java.io.Serializable;
import java.util.*;

public class AlgorithmTest {


    public static void main(String[] args) {


        //eg1:背包问题,限定重量 5kg .
        dpAlgorithm();

        //eg1:多集合交集覆盖范围问题.


    }


    /**
     * 动态规划:背包问题,限定重量 5kg ,选取价值最大的商品组合.(可以重复选取)
     * <p>
     * 问题分析:该类问题,选取个数无限制,唯一限制的是重量(权重).
     * 对于该类问题,使用动态规划的原理是,每个因子,都是可以替换的.
     * 故而可以采用递归选优的方式,层级递归.(这里可以用循环代替,但思想是层级递归)
     * 也就是说,第一层与第二层在限定条件下,选取最优解,选取出来的最优解与第三层比较,选取更优解.
     * 直到所有因子选完,则该解为最优解.
     * <p>
     * ps:此类算法无法解决球队选球员问题.及多集合选取最优解,每个集合只能选取一个.不能解决此问题的原因是,一个球队是一个整体,
     * 这个整体的最优解,来源依赖每一个位置的集合.而每个位置只能有一个人.他的权重比值是分布在整个球员身上.
     * 也无法采用迪克斯特拉算法,因为这里存在限制条件,而这个限制条件是整个球队的.所以球员的限制条件其实是不确定的.如果采用迪克斯特拉算法,
     * 那么,选取出来的路径,可能走不到终点.
     */
    public static void dpAlgorithm() {

        //待选商品
        Product banana = new Product("香蕉", 7, 1);
        Product apple = new Product("苹果", 15, 2);
        Product orange = new Product("桔子", 24, 3);
        Product durian = new Product("榴莲", 31, 4);
        List<Product> products = Lists.newArrayList(apple, banana, durian, orange);
        //100个背包
        for (int i = 0; i < 100; i++) {
            Bag bag = new Bag("小背包" + i, 3 + i, new ArrayList<>(), 0, 0);
            for (int j = 0; j < products.size(); j++) {
                Product product = products.get(j);
                bag = fillBag(bag, product, products);
            }
            System.out.println("背包:" + bag.getBagName() + "\t 总价:" + bag.getSumPrice() + "\t 限重:" + bag.getMaxWeight() + "\t 总重量:" + bag.getSumWeight());
            //输出选取商品名
            String pickName = null;
            List<Product> bagProducts = bag.getProducts();
            for (int j = 0; j < bagProducts.size(); j++) {
                Product product = bagProducts.get(j);
                if (pickName == null) {
                    pickName = product.getName();
                    continue;
                }
                pickName += "-" + product.getName();
            }
            System.out.println("背包:" + bag.getBagName() + "\t 挑选的商品:" + pickName);
        }
    }


    /**
     * 将商品放入背包
     *
     * @param bag
     * @param product
     * @param products
     * @return
     */
    public static Bag fillBag(Bag bag, Product product, List<Product> products) {
        Map<Float, Product> productMap = setupProductMap(products);
        float minWeight = products.stream().min(Comparator.comparing(Product::getWeight)).get().getWeight();
        float maxWeight = bag.getMaxWeight();
        List<Product> pickList = bag.getProducts();
        float sumPrice = bag.getSumPrice();
        float sumWeight = bag.getSumWeight();
        //第一次塞入
        if (CollectionUtils.isEmpty(pickList)) {
            while (sumWeight <= maxWeight - product.getWeight()) {
                pickList.add(product);
                sumWeight += product.getWeight();
                sumPrice += product.getPrice();
            }
        } else {
            //替换
            List<Product> needAdd = new ArrayList<>();
            List<Product> needRemove = new ArrayList<>();
            List<Product> subRemove = new ArrayList<>();
            float removeWeight = 0;
            float removePrice = 0;

            for (int i = 0; i < pickList.size(); i++) {
                Product tmp = pickList.get(i);
                //单个替换
                if (tmp.getPrice() / tmp.getWeight() < product.getPrice() / product.getWeight() && tmp.getWeight() + (maxWeight - sumWeight) >= product.getWeight()) {
                    sumWeight += product.getWeight() - tmp.getWeight();
                    sumPrice += product.getPrice() - tmp.getPrice();
                    needAdd.add(product);
                    needRemove.add(tmp);
                }
                //组合替换
                subRemove.add(tmp);
                removeWeight += tmp.getWeight();
                removePrice += tmp.getPrice();
                if (removePrice / removeWeight < product.getPrice() / product.getWeight() && removeWeight + (maxWeight - sumWeight) >= product.getWeight()) {
                    sumWeight += product.getWeight() - removeWeight;
                    sumPrice += product.getPrice() - removePrice;
                    needAdd.add(product);

                    needRemove.addAll(subRemove);
                    subRemove.clear();
                    removeWeight = 0;
                    removePrice = 0;
                }
                //剩余空间塞值
                float surplus = maxWeight - sumWeight;
                Product surPlus = getSurPlus(products, productMap, surplus);
                while (surplus >= minWeight && surPlus != null) {
                    sumWeight += surPlus.getWeight();
                    sumPrice += surPlus.getPrice();
                    needAdd.add(surPlus);
                    surplus = maxWeight - sumWeight;
                    surPlus = getSurPlus(products, productMap, surplus);
                }
            }
            //删除替换掉的
            Iterator<Product> removes = needRemove.iterator();
            Iterator<Product> pickIt = pickList.iterator();
            while (removes.hasNext()) {
                Product remove = removes.next();
                while (pickIt.hasNext()) {
                    Product pick = pickIt.next();
                    if (pick.equals(remove)) {
                        pickIt.remove();
                        removes.remove();
                        break;
                    }
                }
            }
            pickList.addAll(needAdd);
        }
        bag.setMaxWeight(maxWeight);
        bag.setSumPrice(sumPrice);
        bag.setSumWeight(sumWeight);
        bag.setProducts(pickList);
        return bag;
    }

    /**
     * 获取指定可选重量下,最佳选择的商品
     *
     * @param products
     * @param setupProductMap
     * @param surplus
     * @return
     */
    private static Product getSurPlus(List<Product> products, Map<Float, Product> setupProductMap, float surplus) {
        Product product = setupProductMap.get(surplus);
        if (product != null) {
            return product;
        }
        //重新查找
        for (int i = 0; i < products.size(); i++) {
            Product tmp = products.get(i);
            if (tmp.getWeight() <= surplus) {
                if (product == null) {
                    product = tmp;
                } else if (product.getPrice() < tmp.getPrice()) {
                    product = tmp;
                }
            }
        }
        setupProductMap.put(surplus, product);
        return product;
    }

    /**
     * 相同商品重量的最高价值商品map
     *
     * @param products
     * @return
     */
    public static Map<Float, Product> setupProductMap(List<Product> products) {
        Map<Float, Product> productMap = new HashMap<>();
        for (int i = 0; i < products.size(); i++) {
            Product tmp = products.get(i);
            Product old = productMap.get(tmp.getWeight());
            if (old == null) {
                productMap.put(tmp.getWeight(), tmp);
                continue;
            }
            if (old.getPrice() < tmp.getPrice()) {
                productMap.put(tmp.getWeight(), tmp);
                continue;
            }
        }
        return productMap;
    }


}


/**
 * 背包实体类
 */
class Bag implements Serializable {

    private static final long serialVersionUID = 3554907573665360761L;

    public Bag(String bagName, float maxWeight, List<Product> products, float sumPrice, float sumWeight) {
        this.bagName = bagName;
        this.maxWeight = maxWeight;
        this.products = products;
        this.sumPrice = sumPrice;
        this.sumWeight = sumWeight;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;

        if (!(o instanceof Bag)) return false;

        Bag bag = (Bag) o;

        return new EqualsBuilder()
                .append(getMaxWeight(), bag.getMaxWeight())
                .append(getSumPrice(), bag.getSumPrice())
                .append(getSumWeight(), bag.getSumWeight())
                .append(getBagName(), bag.getBagName())
                .append(getProducts(), bag.getProducts())
                .isEquals();
    }

    @Override
    public int hashCode() {
        return new HashCodeBuilder(17, 37)
                .append(getBagName())
                .append(getMaxWeight())
                .append(getProducts())
                .append(getSumPrice())
                .append(getSumWeight())
                .toHashCode();
    }

    private String bagName;

    private float maxWeight;

    private List<Product> products;

    private float sumPrice;
    private float sumWeight;


    public String getBagName() {
        return bagName;
    }

    public void setBagName(String bagName) {
        this.bagName = bagName;
    }

    public float getMaxWeight() {
        return maxWeight;
    }

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

    public List<Product> getProducts() {
        return products;
    }

    public void setProducts(List<Product> products) {
        this.products = products;
    }

    public float getSumPrice() {
        return sumPrice;
    }

    public void setSumPrice(float sumPrice) {
        this.sumPrice = sumPrice;
    }

    public float getSumWeight() {
        return sumWeight;
    }

    public void setSumWeight(float sumWeight) {
        this.sumWeight = sumWeight;
    }


}

/**
 * 商品实体类
 *
 */
class Product implements Serializable {
    private static final long serialVersionUID = 5594269264643217406L;


    public Product(String name, float price, float weight) {
        this.name = name;
        this.price = price;
        this.weight = weight;
    }

    private String name;

    private float price;

    private float weight;


    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public float getPrice() {
        return price;
    }

    public void setPrice(float price) {
        this.price = price;
    }

    public float getWeight() {
        return weight;
    }

    public void setWeight(float weight) {
        this.weight = weight;
    }
}

---

End