请选择 进入手机版 | 继续访问电脑版

背包问题笔记和代码

[复制链接]
孤单 发表于 2021-1-1 17:46:36 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
笔试题遇到,遗忘了,在此再学习纪录一下
参考:https://www.jianshu.com/p/50af9094a2ac
输入总金额zje和物品数量num、物品单价price、物品重要权重weight,求最大化代价value(每件物品单价*代价 求和)
  1.         public static void main(String[] args) throws Exception {                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                String in = "";                while ((in = br.readLine()) != null && !"".equals(in)) {                        String[] temp = in.split(" ");                        int zje = Integer.parseInt(temp[0]);                        int num = Integer.parseInt(temp[1]);                                                Map map = new HashMap();                        for (int i = 1; i  0; j--) {                                if (j >= goodsPrice) {                                        result[j] = Math.max(result[j - goodsPrice] + goodsPrice * goodsWeight, result[j]);                                }                        }                                                printArr(result);                }                        return result[zje];        }        public static void printArr(int[] values) {                for (int i = 0; i < values.length; i++) {                        System.out.print(values[i] + " ");                }                                System.out.println();        }
复制代码
测试输入输出,为什么一定得从后往前盘算第i行,因为公式中第i行的盘算依赖于第i-1行,使用一维数组后,f[i-1][j - i的单价] 其实就是f[j - 1的单价],如果从前往后盘算,f[j - i的单价]此处的值不再是i-1循环时的值,而是第i次循环重新盘算后的值。
  1. 20 32 3 5 2 6 4 0 0 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0 0 6 6 6 10 10 16 16 16 16 16 16 16 16 16 16 16 16 16 16 0 0 6 6 6 10 24 24 30 30 30 34 34 40 40 40 40 40 40 40 40 ======最大代价====40
复制代码
2、完全背包。所有物品不限量,随便放,其他一样

公式一样,代码从前往后循环便可
  1.         /**         * 完全背包,每次循环从本次物品单价开始,到最大金额         * @param zje         * @param goodsMap         * @return         */        public static int calc2(int zje, Map goodsMap) {                int[] result = new int[zje + 1];                Set keyset = goodsMap.keySet();                for (int key : keyset) {                        String[] valueArr = goodsMap.get(key);                        int goodsPrice = Integer.parseInt(valueArr[0]);                        int goodsWeight = Integer.parseInt(valueArr[1]);                        for (int j = goodsPrice; j  0) {                                        result[i][j] = Math.max(result[i - 1][j - p1] + v1, result[i][j]);                                }                                 if (j >= p2 && p2 > 0){                                        result[i][j] = Math.max(result[i - 1][j - p2] + v2, result[i][j]);                                }                                if (j >= p3 && p3 > 0) {                                        result[i][j] = Math.max(result[i - 1][j - p3] + v3, result[i][j]);                                }                        }                        i++;                }                return result[goodsMap.size()][zje];        }                @SuppressWarnings({ "unchecked", "rawtypes" })        private static void convertGoodsMap(Map goodsMap) {                ArrayList del = new ArrayList();                Set keyset = goodsMap.keySet();                for (int key : keyset) {                        HashMap valueMap = goodsMap.get(key);                        // 主件type 为0,附件type 为主件的编号(map的key)                        int goodsType = (int) valueMap.get("goodsType");                        if (goodsType != 0) {                                // 如果是附件,把附件放到主键对应的map中,key为subGoods                                if (goodsMap.get(goodsType).containsKey("subGoods")) {                                        ((ArrayList)(goodsMap.get(goodsType).get("subGoods"))).add(valueMap);                                } else {                                        ArrayList arrayList = new ArrayList();                                        arrayList.add(valueMap);                                        goodsMap.get(goodsType).put("subGoods", arrayList);                                }                                                                // 删掉原goodsMap信息                                del.add(key);                        }                }                                for (int i = 0; i < del.size(); i++) {                        goodsMap.remove(del.get(i));                }        }
复制代码
测试输入输出
  1. 4500 12100 3 0400 5 0300 5 01400 2 0500 2 0800 2 41400 5 4300 5 01400 3 8500 2 01800 4 0440 5 10======最大代价====16700
复制代码
 

来源:https://blog.csdn.net/xyjy11/article/details/112056584
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )