背包问题

有一个背包，最多放M 的物体（物体大小不限）；
有n个物体，每个物体的重量为，每个物体完全放入背包后可获得收益。问：如何放置能获得最大的收益

• 0/1背包问题

每个物体不可分割，无法使用贪心算法求最优解
全局最优解包含局部最优解
使用动态规划求解，动态规划中最重要的两个概念：状态和状态转移方程
假设物品的体积或重量为V,价值为W

• 状态：d(i,j):前i个宝石装到剩余体积为j的背包里能达到的最大价值
• 状态转移方程：d(i, j)=max{ d(i-1, j), d(i-1,j-V[i-1]) + W[i-1] }讨论前i个宝石装入背包的时候， 其实是在考查第（i-1）个宝石装不装入背包（因为宝石是从0开始编号的）

//n为宝石数量，C为剩余容量
for(int i=0; i<=n; ++i){
    for(int j=0; j<=C; ++j){
        d[i][j] = i==0 ? 0 : d[i-1][j];
        if(i>0 && j>=V[i-1])  d[i][j]  = Math.max(d[i-1][j-V[i-1]]+W[i-1], d[i][j]);
    }
 }

• 一般背包问题

物体可以分割，可以使用贪心算法求最优解
可以计算物体的价值和重量的比值（类似于性价比），由高到低排序，依次选取，最后不能放下的选取它的部分值

public class PakageTest {
    @Data
    @AllArgsConstructor
    class Diamond {
        //diamond id
        private Integer id;
        //diamond price
        private Double price;
        // diamond weight
        private Integer weight;
    }

    List<Diamond> putPackage(List<Diamond> diamonds, Integer m) {
        // 对性价比排序（从高到低排序）
        List<Diamond> sortedDiamonds = diamonds.stream()
                .sorted(Comparator.comparing(diamond -> diamond.getPrice() / diamond.getWeight()))
                .collect(Collectors.toList());
        // 将物体按照性价比从高到低依次加入背包
        int rest = m;// 剩余重量
        int i = 0;
        List<Diamond> results = new ArrayList<>();// 存放结果集
        for (; i < sortedDiamonds.size(); i++) {
            if (rest < sortedDiamonds.get(i).getWeight())
                break;
            Diamond curDiamond = diamonds.get(i);
            results.add(curDiamond);
            rest -= curDiamond.getWeight();
        }
        // 计算最后一个物体能放入的部分
        Diamond lastDiamond = sortedDiamonds.get(i);
        results.add(new Diamond(lastDiamond.id, (lastDiamond.getPrice() * rest / lastDiamond.getWeight()), rest));
        return results;
    }
}