Java题目训练——求正数数组的最小不可组成和和有假币

末蓝、 2023-09-30 23:01 42阅读 0赞

**目录**

一、求正数数组的最小不可组成和

二、有假币

--------------------

### 一、求正数数组的最小不可组成和 ###

题目描述：

> 给定一个全是正数的数组arr，定义一下arr的最小不可组成和的概念： 1，arr的所有非空子集中，把每个子集内的所有元素加起来会出现很多的值，其中最小的 记为min，最大的记为max； 2，在区间\[min,max\]上，如果有一些正数不可以被arr某一个子集相加得到，那么这些正数中最小的那个，就是arr的最小不可组成 和； 3，在区间\[min,max\]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和； 举例： arr = \{3,2,5\} arr的min为2， max为10，在区间\[2,10\]上，4是不能被任何一个子集相加得到的值中最小的，所以4是arr的最小不可组成和； arr = \{3,2,4\} arr的min为2，max为9，在区间 \[2,9\]上，8是不能被任何一个子集相加得到的值中最小的，所以8是arr的最小不可组成和； arr = \{3,1,2\} arr的min为1，max为6，在区间\[2,6\]上，任何数都可以 被某一个子集相加得到，所以7是arr的最小不可组成和； 请写函数返回arr的最小不可组成和。

**题目解析：**

> 本题的思路主要是利用动态规划算法，这个问题具体是背包问题的变形，背包容量的范围在【min，max】,dp数组相当于每个物品的重量，如果背包容量和所承载的物品重量不相等，就是所求，可以转换的原因是：背包容量\[min,max\]是数组的子集之和的范围。
> 
> 比如数组2 3 4，背包从2~9,背包2号承载了子集2的和，背包5就是子集2,3的和，这里的2，3，4就可看作是元素权重，而某一个背包如果不能承载这些权重，就不是子集之和。
> 
> 首先求得区间范围的min和max，然后建立状态数组dp记录该元素，寻找状态方程和初始化状态。
> 
> 转换为背包问题的话，数组dp下标表示这个编号对应的最大容量，数组dp值表示价值。
> 
> 状态方程我们可以这样考虑，从max开始，max肯定是可以组成的，状态就是dp\[j\]表示最大容量是j时，存储的最大容量。如果j比arr\[i\]小，说明背包容量不足以存放当前元素，那么就让他继续存放i - 1元素的值即可，不用做处理；如果空间容量足够，那么就要在多个元素组合和一个元素（当前元素 或者 i - 1元素）中选择最大值。
> 
> 这里注意为什么要从后往前遍历，因为从前往后遍历可能会出现同一个元素重复使用的情况。

import java.util.*;
    public class Solution {
    /**
    * 正数数组中的最小不可组成和
    * 输入：正数数组arr
    * 返回：正数数组中的最小不可组成和
    */
    public int getFirstUnFormedNum(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            if(min > arr[i]) {
                min = arr[i];
            }
            max += arr[i];
        }
        int[] dp = new int[max + 1];
        //把东西依次放入背包
        for (int i = 0; i < arr.length; i++) {
            for (int j = max; j >= arr[i] ; j--) {
                //逆序判断背包承重中能够放入的数据
                dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
            }
        }
        for (int i = min; i <= max; i++) {
            if(dp[i] != i){
                return i;
            }
        }
        return max + 1;
        }
    }

### 二、有假币 ###

题目描述：

> 居然有假币！ 现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。nowcoder这就去买猪肉，结果找来的零钱中有假币！！！可惜nowcoder 一不 小心把它混进了一堆真币里面去了。只知道假币的重量比真币的质量要轻，给你一个天平（天平两端能容纳无限个硬币），请用最快的时间把那个可恶的假币找 出来。

输入描述：

> 1≤n≤2^30,输入0结束程序。

输出描述：

> 最多要称几次一定能把那个假币找出来？

示例

> 输入：3
> 
> 12
> 
> 0
> 
> 输出：1
> 
> 3

**题目解析：**

> 因为要用最快的方式，那我们一开始就把硬币分成3堆；因为要求最多称几次，所以我们考虑假币一直在数量最多的硬币堆中。
> 
> 设硬币堆的数量为n，如果正好能分成3堆，即如果n % 3 == 0,分成 n/3、 n/3、 n/3三堆， 那么硬币堆n = n / 3，剩下 n/3；如果不能正好分成3堆，多出来2个或者1个，最多堆都是再加1个：
> 
> 如果n % 3 == 1,分成 n/3、 n/3、1 + (n/3)三堆，最坏剩下 1 + (n/3)；  
> 如果n % 3 == 2,分成 n/3、 1 + (n/3)、1 + (n/3)三堆，最坏剩下 1 + (n/3)。
> 
> 直到最后n变成1个，找到假币，在找的过程中设置一个计数器变量count记录循环了多少次即最多需要称多少次。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNext()){
                int n = scanner.nextInt();
                if(n == 0){
                    break;
                }
                System.out.println(findNum(n));
            }
        }
    
        public static int findNum(int n){
            int count = 0;
            //需要称
            while(n >= 2){
            count++;
            //题目要求最多的次数，假设假币一直在数量最多的硬币堆中
            if(n % 3 == 0){
                //能正好分成3堆
                n = n / 3;
            }else{
                //不能正好分成3堆
                //多出来2个或者1个，最多堆都是再加1个
                //如果n % 3 == 0,分成 n/3、 n/3、 n/3三堆， 剩下 n/3
                //如果n % 3 == 1,分成 n/3、 n/3、1 + (n/3)三堆，最坏剩下 1 + (n/3)
                //如果n % 3 == 2,分成 n/3、 1 + (n/3)、1 + (n/3)三堆，最坏剩下 1 + (n/3)
                n = n / 3 + 1;
            }
        }
        return count;
        }
    }

如有建议或想法，欢迎一起讨论学习~