# stage10-1

**Repository Path**: null_631_9084/stage10-1

## Basic Information

- **Project Name**: stage10-1
- **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-01-23
- **Last Updated**: 2021-01-23

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

package com.liu.test;

import org.junit.Test;

/**
 * ---------------------------------------------------------------------------
 * 类名称   ：WorkerTest.java
 * 类描述   ：
 * 创建时间 ：2021/1/23 9:39
 * @author ： liunan
 * ---------------------------------------------------------------------------
 */
public class WorkerTest {

    public static final int SIZE = 256;

    /**
     * 作业一
     * 判断数组中所有的数字是否只出现一次。给定一个数组array，判断数组 array 中是否所有的数字都只出现过一次。例如，arr = {1, 2, 3}，输出 YES。又如，arr = {1, 2, 1}，输出 NO。约束时间复杂度为 O(n)。
     */
    @Test
    public void work1Test() {
        int[] arr = {1, 2, 3};

        System.out.println(work1Do(arr));
        int[] arr2 = {1, 2, 1};

        System.out.println(work1Do(arr2));

    }

    public boolean work1Do(int[] arr) {
        // 计数法思路，使用boolean 数组存储值，循环遍历依次放入数组，判断如存在则说明重复
        boolean[] comArr = new boolean[SIZE];

        for (int i = 0; i < arr.length; i++) {
            if (comArr[arr[i]]) {
                return false;
            } else {
                comArr[arr[i]] = true;
            }
        }
        return true;

    }


    /**
     * 作业一
     * 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。
     * 例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人来挖掘……
     * 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。
     * 要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
     */
    @Test
    public void work2Test() {
        int w = 10;
        int[] p = {5, 5, 3, 4, 3};
        int[] g = {400, 500, 200, 300, 350};
        System.out.println("最优收益：" + getBestGoldMining(w, g.length, p, g));
    }

    /**
     * 获得金矿最优收益
     *
     * @param w 工人数量
     * @param n 可选金矿数量
     * @param p 金矿开采所需的工人数量
     * @param g 金矿储量
     * @return
     */
    //递归进行求解
    public static int getBestGoldMining(int w, int n, int[] p, int[] g) {
        if (w == 0 || n == 0) {
            return 0;
        }
        if (w < p[n - 1]) {
            return getBestGoldMining(w, n - 1, p, g);
        }
        return Math.max(getBestGoldMining(w, n - 1, p, g), getBestGoldMining(w - p[n - 1], n - 1, p, g) + g[n - 1]);
    }

    /**
     * 获得金矿最优收益
     *
     * @param w 工人数量
     * @param p 金矿开采所需的工人数量
     * @param g 金矿数量
     * @return
     */
    //递归做了很多重复的计算，当金矿越来越多，递归层次越来越深，重复调用也就越来越多，无谓的调用必然会降低程序的性能
    //利用双循环来填充一个二维数组，时间复杂度和空间复杂度都是O(nw)
    public static int getBestGoldMiningV2(int w, int[] p, int[] g) {
        //创建表格
        int[][] resultTable = new int[g.length + 1][w + 1];
        //填充表格
        for (int i = 1; i <= g.length; i++) {
            for (int j = 1; j <= w; j++) {
                if (j < p[i - 1]) {
                    resultTable[i][j] = resultTable[i - 1][j];
                } else {
                    resultTable[i][j] = Math.max(resultTable[i - 1][j], resultTable[i - 1][j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        //返回最后1个格子的值
        return resultTable[g.length][w];
    }

    // 并不需要保存整个表格，无论金矿多少座，我们只保存1行的数据即可，在计算下一行时，要从右向左统计，把旧的数据一个一个替换掉
    //时间复杂度是O(nw) 空间复杂度是O(n)

    /**
     * 获得金矿最优收益
     *
     * @param w 工人数量
     * @param p 金矿开采所需的工人数量
     * @param g 金矿数量
     * @return
     */
    public static int getBestGoldMiningV3(int w, int[] p, int[] g) {
        //创建当前结果
        int[] results = new int[w + 1];
        //填充一维数组
        for (int i = 1; i <= g.length; i++) {
            for (int j = w; j >= 1; j--) {
                if (j >= p[i - 1]) {
                    results[j] = Math.max(results[j], results[j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        //返回最后一个格子的值
        return results[w];
    }
}