# stage10-01

**Repository Path**: cllyl/stage10-01

## Basic Information

- **Project Name**: stage10-01
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-05-14
- **Last Updated**: 2021-05-14

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 背包问题

## 前言

贪心算法解决部分背包问题

动态对话（Dynamic Programming）解决0-1背包问题

## 0-1背包问题

#### 问题描述

有1个背包，能承受的最大重量为W

有N件物品，每件物品的重量为W[i]，价值为V[i]

每件物品只能放进去0或者1次

求背包能够承受的最大价值是多少

#### 问题分析

由质分析，转换为定量分析。

假设：

背包总重量为10

共有5件物品

|                    | 重量（Weight） | 价值（Value） |
| ------------------ | -------------- | ------------- |
| 0（W[0]=2,V[0]=6） | 2              | 6             |
| 1（W[1]=2,V[1]=3） | 2              | 3             |
| 2（W[2]=6,V[2]=5） | 6              | 5             |
| 3（W[3]=5,V[3]=4） | 5              | 4             |
| 4（W[4]=4,V[4]=6） | 4              | 6             |

###### 承重分析

横轴为最大重量

纵轴为物品信息

表格中显示的是对应重量物品的价值，最大价值（最优解）

| dp(i,j)            | 0    | 1    | 2      | 3      | 4      | 5      | 6      | 7      | 8       | 9      | 10     |
| ------------------ | ---- | ---- | ------ | ------ | ------ | ------ | ------ | ------ | ------- | ------ | ------ |
| 空（W=0,V=0）      | 0    | 0    | 0      | 0      | 0      | 0      | 0      | 0      | 0       | 0      | 0      |
| 0（W[0]=2,V[0]=6） | 0    | 0    | 6（0） | 6（0） | 6（0） | 6（0） | 6（0） | 6（0） | 6（0）  | 6（0） | 6（0） |
| 1（W[1]=2,V[1]=3） | 0    | 0    | 6(0)   | 6(0)   | 9(0,1) | 9(0,1) | 9(0,1) | 9(0,1) | 9(0,1)  | 9(0,1) | 9(0,1) |
| 2（W[2]=6,V[2]=5） | 0    | 0    | 6(0)   | 6(0)   | 9(0,1) | 9(0,1) | 9(0,1) | 9(0,1) | 11(0,2) | 11     | 11     |
| 3（W[3]=5,V[3]=4） | 0    | 0    | 6      | 6      | 9      | 9      | 9      | 10     | 11      | 13     | 14     |
| 4（W[4]=4,V[4]=6） | 0    | 0    | 6      | 6      | 9      | 9      | 12     | 12     | 15      | 15     | 15     |

dp(0,2)的时候，添加0

dp(1,2)的时候，不添加，不移除，保持不变

dp(1,4)的时候，添加1，不移除

dp(2,8)的时候，可以选择当前2号商品，

如上图标可以按照一下思路分析

向背包中添加物品。

添加物品分为一下三种情况

- 可以添加
  - 添加
  - 不添加
- 不可以添加

> 不可以添加

$j<w[i]$





不能向背包中添加商品了，以上表中背包重量为0为例，dp(1,0) = dp(0, 1),代表添加这一件物品之后，背包超重，并且没有替换的物品了。

重点注意事项

- 不可以添加

  最优解就是：不包含当前物品的时候的最优解

  物品就是：不包含当前物品的时候的最优解的物品数量

- 可以添加的情况下不添加

  最优解就是：不包含当前物品的时候的最优解

  物品就是：不包含当前物品的时候的最优解的物品数量

- 可以添加的情况下添加

  最优解就是：当前物品的价值 + 背包减去该物品的重量的时候，不包含该物品的最优解

  物品就是：背包减去该物品的重量，并且不包含该物品的最优解的时候的物品 + 该物品

## 作业习题

#### 数字重复问题

**作业一：数据结构与算法基础** 

判断数组中所有的数字是否只出现一次。给定一个数组array，判断数组 array 中是否所有的数字都只出现过一次。例如，arr = {1, 2, 3}，输出 YES。又如，arr = {1, 2, 1}，输出 NO。约束时间复杂度为 O(n)。

````java
package com.cll.learn.stage10.example1;

import java.util.*;

/**
 * 描述信息:
 * 检测数组中元素是否唯一
 * @author CLL
 * @version 1.0
 * @date 2021/5/12 18:02
 */
public class CheckUnique {

    public static void main(String[] args) {
        int[] arr = new int[]{2,4,6,8,6,12};
        String result = checkArrayUnique(arr);
        System.out.println("result = " + result);
    }

    private static String checkArrayUnique(int[] array){
        Set<Integer> arrSet = new HashSet<>();
        for (int j : array) {
            if (arrSet.contains(j)) {
                return "NO";
            }
            arrSet.add(j);
        }
        return arrSet.size() == array.length ? "YES" : "NO";
    }
}
````

#### 背包作业

**作业二：数据结构与算法高级** 

很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人 来挖掘。 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

根据题目可知，不仅需要最优解，还需要最优解对应的金矿资源信息。根据题意构造方法如下

###### 构造金矿资源对象

````java
package com.cll.learn.stage10.example2;

/**
 * 描述信息:
 * 黄金资源
 * @author CLL
 * @version 1.0
 * @date 2021/5/13 8:22
 */
public class GoldResource {


    /**
     * 开采当前资源需要的人力，相当于物品重量
     */
    private int person;

    /**
     * 当前黄金容量,相当于物品价值
     */
    private int capacity;

    public GoldResource(int person, int capacity) {
        this.person = person;
        this.capacity = capacity;
    }

    @Override
    public String toString() {
        return "GoldResource{" +
                "person=" + person +
                ", capacity=" + capacity +
                '}';
    }

    public int getPerson() {
        return person;
    }

    public void setPerson(int person) {
        this.person = person;
    }

    public int getCapacity() {
        return capacity;
    }

    public void setCapacity(int capacity) {
        this.capacity = capacity;
    }

}
````

###### 构造国王对象

````java
package com.cll.learn.stage10.example2;

import java.util.ArrayList;
import java.util.List;

/**
 * 描述信息:
 * 国王对象
 * @author CLL
 * @version 1.0
 * @date 2021/5/13 8:25
 */
public class King {

    /**
     * 国王拥有的矿工的人数，相当于背包容量
     */
    private int person;

    /**
     * 国王拥有的矿产信息
     */
    private List<GoldResource> goldResourceList;

    /**
     * 获取当前情况下国王选择近况资源的信息
     * @return  包含最优解，以及最优解对应的金矿资源信息
     */
    public Result selectGoldResourceResult(){
        if (0 >= person) {
            return new Result(0, new ArrayList<>());
        }
        if (null == goldResourceList || 0 == goldResourceList.size()) {
            return new Result(0, new ArrayList<>());
        }
        // 本轮选择的金矿资源
        List<GoldResource> result = new ArrayList<>();
        // 本轮最优解
        int resultCapacity = 0;
        // 当前可以选择的金矿资源
        List<GoldResource> currentGoldResource = new ArrayList<>();
        for (GoldResource goldResource : goldResourceList) {

            // 不可选情况
            if (goldResource.getPerson() > person) {
                Result preResult = new King(person, currentGoldResource).selectGoldResourceResult();
                resultCapacity = preResult.getCapacity();
                result = preResult.getSelectGoldResource();
            } else {
                // 可选情况下不选
                Result preResult = new King(person, currentGoldResource).selectGoldResourceResult();
                int notSelectCapacity = preResult.getCapacity();
                List<GoldResource> notSelectGoldResourceList = preResult.getSelectGoldResource();

                // 可选情况下选择
                Result currentResult = new King(person - goldResource.getPerson(), currentGoldResource).selectGoldResourceResult();
                int selectCapacity = goldResource.getCapacity() + currentResult.getCapacity();
                List<GoldResource> selectGoldResourceList = new ArrayList<>(currentResult.getSelectGoldResource());
                selectGoldResourceList.add(goldResource);

                resultCapacity = Math.max(notSelectCapacity, selectCapacity);

                if (selectCapacity == Math.max(notSelectCapacity, selectCapacity)) {
                    // 选择了
                    result = selectGoldResourceList;
                } else {
                    result = notSelectGoldResourceList;
                }
                // 将当前矿产添加到可以选择矿产列表
                currentGoldResource.add(goldResource);
            }
        }
        return new Result(resultCapacity, result);
    }

    public King(int person, List<GoldResource> goldResourceList) {
        this.person = person;
        this.goldResourceList = goldResourceList;
    }

    public int getPerson() {
        return person;
    }

    public void setPerson(int person) {
        this.person = person;
    }

    public List<GoldResource> getGoldResourceList() {
        return goldResourceList;
    }

    public void setGoldResourceList(List<GoldResource> goldResourceList) {
        this.goldResourceList = goldResourceList;
    }


    @Override
    public String toString() {
        return "King{" +
                "person=" + person +
                ", goldResourceList=" + goldResourceList.toString() +
                '}';
    }
}
````

###### 构造返回结果

````java
package com.cll.learn.stage10.example2;

import java.util.List;

/**
 * 描述信息:
 *
 * @author CLL
 * @version 1.0
 * @date 2021/5/14 9:27
 */
public class Result {

    /**
     * 当前的最优解
     */
    private int capacity;

    /**
     * 当前最优解对应的金矿资源序号
     */
    private List<GoldResource> selectGoldResource;

    public Result() {
    }

    public Result(int capacity, List<GoldResource> selectGoldResource) {
        this.capacity = capacity;
        this.selectGoldResource = selectGoldResource;
    }

    @Override
    public String toString() {
        return "Result{" +
                "capacity=" + capacity +
                ", selectGoldResource=" + selectGoldResource +
                '}';
    }

    public int getCapacity() {
        return capacity;
    }

    public void setCapacity(int capacity) {
        this.capacity = capacity;
    }

    public List<GoldResource> getSelectGoldResource() {
        return selectGoldResource;
    }

    public void setSelectGoldResource(List<GoldResource> selectGoldResource) {
        this.selectGoldResource = selectGoldResource;
    }
}

````

###### 构造测试类

````java
package com.cll.learn.stage10.example2;

import java.util.ArrayList;
import java.util.List;

/**
 * 描述信息:
 *
 * @author CLL
 * @version 1.0
 * @date 2021/5/13 20:50
 */
public class Test {

    public static void main(String[] args) {
        // 背包容量
        int person = 10;
        List<GoldResource> goldResourceList = new ArrayList<>(5);
        // 金矿耗费人力为2，容量为600
        GoldResource goldResource1 = new GoldResource(2, 600);
        GoldResource goldResource2 = new GoldResource(2, 300);
        GoldResource goldResource3 = new GoldResource(6, 500);
        GoldResource goldResource4 = new GoldResource(5, 400);
        GoldResource goldResource5 = new GoldResource(4, 600);

        goldResourceList.add(goldResource1);
        goldResourceList.add(goldResource2);
        goldResourceList.add(goldResource3);
        goldResourceList.add(goldResource4);
        goldResourceList.add(goldResource5);

//        GoldResource goldResource1 = new GoldResource(2, 3);
//        GoldResource goldResource2 = new GoldResource(3, 4);
//        GoldResource goldResource3 = new GoldResource(4, 5);
//        GoldResource goldResource4 = new GoldResource(5, 6);
//
//        goldResourceList.add(goldResource1);
//        goldResourceList.add(goldResource2);
//        goldResourceList.add(goldResource3);
//        goldResourceList.add(goldResource4);

        King king = new King(person, goldResourceList);

        Result result = king.selectGoldResourceResult();
        System.out.println("最终产生的最优解 = " + result.toString());
    }
}

````

> 测试类返回执行结果

````java
最终产生的最优解 = Result{capacity=1500, selectGoldResource=[GoldResource{person=2, capacity=600}, GoldResource{person=2, capacity=300}, GoldResource{person=4, capacity=600}]}

````