美文网首页
背包问题

背包问题

作者: whupenger | 来源:发表于2019-03-08 10:30 被阅读0次

有一个背包,最多放M kg的物体(物体大小不限);
有n个物体,每个物体的重量为W_i,每个物体完全放入背包后可获得收益P_i。问:如何放置能获得最大的收益

  • 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;
    }
}

相关文章

  • 背包问题(完全背包)

    动态规划合集: 1.矩阵链乘法2.投资组合问题3.完全背包问题4.01背包问题5.最长公共子序列 例题3——背包问...

  • Algorithm进阶计划 -- 动态规划(下)

    经典动态规划背包问题最长子序列问题 1. 背包问题 1.1 0-1 背包问题 0-1 背包问题,描述如下: 上面...

  • 背包问题

    0-1背包问题 问题 n个物体,它们各自有重量和价值,给定一个有容量的背包,如何让背包里装入的物体价值总和最大? ...

  • 背包问题

    问题描述 假如有一个能装下4磅的背包,如何从下列商品列表中选择商品填充背包,使价值达到最大: 动态规划 要解决背包...

  • 背包问题

    (1)0-1背包容量为10的背包,有5种物品,每种物品只有一个,其重量分别为5,4,3,2,1,其价值分别为1,2...

  • 背包问题

  • 背包问题

    01背包(物品只有一个) 有N件物品和一个容量为V的背包。第i建物品的费用是w[i],价值是v[i]。求解将哪些物...

  • 背包问题

    1. 01背包 状态说明:背包体积为v,物品个数为n,f[n,v]表示前n件物品加入背包的最大价值。c_i,w_i...

  • 背包问题

    01背包 优化空间复杂度,变为一维; 外循环依然是n从1->N, 注意内循环 v是从V->0,为什么内循环是V->...

  • 背包问题

    介绍 学习动态规划算法的经典例题。动态规划算法一般有3个特征1、最优化原理:最优解所包含的子问题的解也是最优的。2...

网友评论

      本文标题:背包问题

      本文链接:https://www.haomeiwen.com/subject/phrkpqtx.html