栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

蛮力法/01背包问题

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

蛮力法/01背包问题

  • 所有解:结合增量蛮力法 求解幂集的方法,先求出所有物品的组合
  • 可行解:遍历所有的物品求物品和体积<=背包容量的物品组合
  • 最优解:找出体积和最大的物品组合
package xcrj.kchalgorithm.bruteForce;

import java.util.*;


public class Knapsack01 {

    static class Goods {
        private int weight;
        private int value;

        public Goods() {
        }

        public Goods(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }

        public int getWeight() {
            return weight;
        }

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

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }
    }

    
    public static Set> feasibleResults(Set> allResult, int availableWeight, int[] weights, int[] values) {
        Set> feasibleWeightResult = new HashSet<>(8);
        Set optimalValueResult = null;
        int optimalValue = 0;
        for (Set set : allResult) {
            int weightSum = 0;
            for (Integer code : set) {
                weightSum += weights[code - 1];
            }
            // 可以放进背包的物品
            if (weightSum <= availableWeight) {
                Set feasibleSet = new HashSet<>(4);
                for (Integer code : set) {
                    feasibleSet.add(code);
                }
                feasibleWeightResult.add(feasibleSet);
                // 可以放进背包的物品价值
                int sumValue = 0;
                for (Integer code : set) {
                    sumValue += values[code - 1];
                }
                // 最大价值
                if (sumValue > optimalValue) {
                    optimalValue = sumValue;
                    optimalValueResult = new HashSet<>(4);
                    for (Integer code : set) {
                        optimalValueResult.add(code);
                    }
                }
            }
        }

        System.out.println("所有可行解:");
        System.out.println(feasibleWeightResult);

        System.out.println("最优解:");
        System.out.println(optimalValueResult);
        return feasibleWeightResult;
    }

    
    public static Set> allResults(int n) {
        Set> setSet = new HashSet<>(8);
        // {} 空集
        Set setNull = new HashSet<>();
        setSet.add(setNull);

        for (int j = 0; j < n; j++) {
            Set> setSet2 = new HashSet<>(8);
            // 保存原来的集合
            for (Set set : setSet) {
                Set set2 = new HashSet<>();
                for (Integer v : set) {
                    set2.add(v);
                }
                setSet2.add(set2);
            }

            // 给原集合中的每个幂集增加j
            for (Set set : setSet) {
                set.add(j + 1);
            }

            // 将set2中的幂集放到set中,组合成新的集合
            for (Set set : setSet2) {
                setSet.add(set);
            }
        }

        return setSet;
    }

    public static void main(String[] args) {
        // 4个物品,能承受6公斤重量的背包
        // 数组下标+1是物品的唯一编号
        int[] weights = {5, 3, 2, 1};
        int[] valuess = {4, 4, 3, 1};
        Set> allResult = allResults(4);
        feasibleResults(allResult, 6, weights, valuess);
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/951050.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号