2020秋招-小米笔试题-小米之家购物

年轻即出发...

简书：https://www.jianshu.com/u/7110a2ba6f9e

知乎：https://www.zhihu.com/people/zqtao23/posts

GitHub源码：https://github.com/zqtao2332

个人网站：http://www.zqtaotao.cn/ （停止维护更新内容）

QQ交流群：606939954

​ 咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。

最后：喜欢编程，对生活充满激情

---

---

本节内容预告

2020秋招-小米笔试题-小米之家购物

---

---

2020秋招-小米笔试题-小米之家购物

小米之家购物 ---> N 元钱最少能买几件，求最少not最多

时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：
小米之家有很多米粉喜欢的产品，产品种类很多，价格也不同。比如某签字笔1元，某充电宝79元，某电池1元，某电视1999元等

假设库存不限，小明去小米之家买东西，要用光N元预算的钱，请问他最少能买几件产品？

输入

第1行为产品种类数

接下来的每行为每种产品的价格

最后一行为预算金额

输出

能买到的最少的产品的件数，无法没有匹配的返回-1

样例输入

2
500
1
1000

样例输出

2

动态规划

动态规划
dp[i][j] 表示在可以使用 arr[0..i] 任意货币的情况下，组成 j 需要的最小张数
@param arr 货币价值
@param aim 目标值
@return 组成 aim 最少需要货币张数
     *
完全不使用当前货币arr[i]情况下的最少张数,即 dpl[i-1][j]的值
只使用1张当前货币arr[i]情况下的最少张数,即 dp[i-1][j-arr[i]] + 1
只使用2张当前货币arr[i]情况下的最少张数,即 dp[i-1][j-2*arr[i]] + 2
只使用3张当前货币arr[i]情况下的最少张数,即 dp[i-1][j-3*arr[i]] + 3
     *
总结所有情况下，最终取最小张数
dp[i][j]=min{dp[i-1][j-K*arr[i]] + K}  (K >= 0)
     *
简化依赖
dp[i][j]=min{dp[i-1][j], dp[i][j-arr[i]] + 1}
其中 j-arr[i] <0 时越界，说明arr[i] 值太大，用一张货币都会超过钱数 j
     *
dp[i][j] 依赖左边一个值和上边一个值

package cn.zqtao.examintion;


/**
 * 小米之家购物 --->  N 元钱最少能买几件，求最少not最多
 * 时间限制：C/C++语言 1000MS；其他语言 3000MS
 * 内存限制：C/C++语言 65536KB；其他语言 589824KB
 * 题目描述：
 * 小米之家有很多米粉喜欢的产品，产品种类很多，价格也不同。比如某签字笔1元，某充电宝79元，某电池1元，某电视1999元等
 *
 * 假设库存不限，小明去小米之家买东西，要用光N元预算的钱，请问他最少能买几件产品？
 *
 * 输入
 * 第1行为产品种类数
 *
 * 接下来的每行为每种产品的价格
 *
 * 最后一行为预算金额
 *
 *
 * 输出
 * 能买到的最少的产品的件数，无法没有匹配的返回-1
 *
 *
 * 样例输入
 * 2
 * 500
 * 1
 * 1000
 * 样例输出
 * 2
 */
public class Code_04_MinItemByAllMoney {
    public static int solution(int[] prices, int budget) {
        if (prices == null || prices.length == 0 || budget < 0) return  -1;

        int n = prices.length;
        int max = Integer.MAX_VALUE;
        int[][] dp = new int[n][budget+1];
        for (int j = 1; j <= budget; j++) {
            dp[0][j] = max;
            if (j - prices[0] >= 0 && dp[0][j - prices[0]] != max){
                dp[0][j] = dp[0][j - prices[0]] + 1;
            }
        }
        int left = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= budget; j++) {
                left = max;
                if (j - prices[i] >= 0 && dp[i][j - prices[i]] != max){
                    left = dp[i][j - prices[i]] + 1;
                }
                dp[i][j] = Math.min(left, dp[i - 1][j]);
            }
        }
        return dp[n - 1][budget] != max ? dp[n - 1][budget] : -1;
    }

    public static void main(String[] args) {
        int[] arr = {500, 1};
        System.out.println(solution(arr, 2001));
    }
}

压缩动态规划表空间

     public static int minCoin2(int[] prices, int budget) {
        if (prices == null || prices.length == 0 || budget < 0) return -1;

        int[] dp = new int[budget+1];
        int max = Integer.MAX_VALUE;

        for (int j = 1; j <= budget; j++) { // 初始化第一行，只是用prices[0] 的情况下
            dp[j] = max;
            if (j - prices[0] >= 0 && dp[j - prices[0]] != max) {
                dp[j] = dp[j - prices[0]] + 1;
            }
        }

        int left = 0;
        for (int i = 1; i < prices.length; i++) {
            for (int j = 1; j <= budget; j++) {
                left = max;
                if (j - prices[i] >= 0 && dp[j - prices[i]] != max){
                    left = dp[j - prices[i]] + 1;
                }
                dp[j] = Math.min(dp[j], left);
            }
        }
        return dp[budget] == max ? -1 : dp[budget];
    }