java实现01背包问题(动态规划)和集合覆盖问题(贪心算法)

01背包问题(动态规划)

package com.csw.algorithm.dynamic;

import java.util.Arrays;

/**
 * @Auther: 行路
 * @Date: Created on 2020/5/3 15:35 星期天
 * @Description: com.csw.algorithm.dynamic
 * @version: 1.0
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w = {1, 4, 3}; //物品的重量
        int[] val = {1500, 3000, 2000}; //物品的价值
        int m = 4; //背包的容量
        int n = val.length; //物品的个数
        //创建二位数组
        //v[i][j]表示在前i个物品中能够装入容量为j的背包最大价值
        int[][] v = new int[n + 1][m + 1];

        //为了记录放入商品的情况,我们定义一个二维数组
        int[][] path = new int[n + 1][m + 1];

        //初始化第一行和第一列,在本程序中默认就是0
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0; //将第一列设置为0
        }
        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0; //将第一行设置为0
        }

        //根据公式进行动态规划
        for (int i = 1; i < v.length; i++) {
            //不处理第一行
            for (int j = 1; j < v[0].length; j++) {
                //不处理第一列
                if (w[i - 1] > j) { //因为程序从1开始
                    v[i][j] = v[i - 1][j];
                } else {
                    //因为i是从1开始的,所以公式需要调整
                    //v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
                    //为了记录商品存放到背包的情况,我们不能直接使用上面的公式,需要使用if-else来体现公式
                    if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        //把当前的情况记录到path
                        path[i][j] = 1;
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }

        //输出一下v
//        for (int i = 0; i < v.length; i++) {
//            for (int j = 0; j < v[i].length; j++) {
//                System.out.print(v[i][j] + " ");
//            }
//            System.out.println("");
//        }

        //输出一下v
        //这样输出不对
//        for (int i = 0; i < v.length; i++) {
//            for (int j = 0; j < v[i].length; j++) {
//                // System.out.print(path[i][j]+" ");
//                if (path[i][j] == 1) {
//                    System.out.printf("第%d个商品放入到背包\n", i);
//                }
//            }
//        }

        for(int[] a:v){
            System.out.println(Arrays.toString(a));
        }

        for(int[] a:path){
            System.out.println(Arrays.toString(a));
        }
        int i=path.length-1;
        int j=path[0].length-1;
        while (i>0&&j>0){
            if(path[i][j]==1){
                System.out.printf("第%d个商品放入到背包\n",i);
                j-=w[i-1];
            }
            i--;
        }

    }
}

集合覆盖问题(贪心算法)

package com.csw.algorithm.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @Auther: 行路
 * @Date: Created on 2020/5/4 21:23 星期一
 * @Description: com.csw.algorithm.greedy
 * @version: 1.0 贪心算法
 */
public class GreedyAlgorithm {
    public static void main(String[] args) {
        //创建广播电台,放入到Map
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        //将各个电台放入到broadcasts
        HashSet<String> hashSet1=new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");

        HashSet<String> hashSet2=new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");

        HashSet<String> hashSet3=new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");

        HashSet<String> hashSet4=new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");

        HashSet<String> hashSet5=new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");

        broadcasts.put("k1",hashSet1);
        broadcasts.put("k2",hashSet2);
        broadcasts.put("k3",hashSet3);
        broadcasts.put("k4",hashSet4);
        broadcasts.put("k5",hashSet5);

        HashSet<String> allAreas = new HashSet<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");

        //创建一个ArrayList,存放电台集合
        ArrayList<String> selects = new ArrayList<>();

        //定义一个临时集合,在遍历过程中,存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
        HashSet<String> tempSet = new HashSet<String>();

        //定义一个maxKey,保存在一次遍历过程中,能够覆盖最大未覆盖的地区对应的电台的Key
        //如果maxKey 不为null,则会加入到selects
        String maxKey=null;
        while (allAreas.size()!=0){
            //没进行一次while,需要
            maxKey=null;

            //如果allAreas不为0说明还没有覆盖所有地区
            //遍历 broadcasts,取出对应的key
            for(String key:broadcasts.keySet()){
                //没进行一次for
                tempSet.clear();
                //当前这个Key能覆盖的地区
                HashSet<String> areas = broadcasts.get(key);
                tempSet.addAll(areas);
                //求出tempSet和allAreas集合的交集,交集会赋给tempSet
                tempSet.retainAll(allAreas);
                //如果当前集合包含未覆盖地区的数量比maxKey指向的集合未覆盖的地区还多
                if(tempSet.size()>0&&(maxKey==null||tempSet.size()>broadcasts.get(maxKey).size())){
                    maxKey=key;
                }
            }
            //maxKey!=null,就应该将maxKey加入selects中
            if(maxKey!=null){
                selects.add(maxKey);
                //将maxKey指向的广播电台覆盖的地区,从allAreas去掉
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        System.out.println("得到的选择结果集合"+selects);
    }
}