2017网易---买苹果

题目描述

小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。

输入描述:

输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果

输出描述:

输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1

示例1

输入

输出

3

题目链接：https://www.nowcoder.com/practice/61cfbb2e62104bc8aa3da5d44d38a6ef?tpId=85&tqId=29856&tPage=1&rp=1&ru=/ta/2017test&qru=/ta/2017test/question-ranking

法一：dfs，深搜直接计数，比大小。注意后面sum要回溯。代码如下（耗时9ms）：

 1 public class Main {
 2 
 3     public static void main(String[] args) throws IOException {
 4         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 5         String line = in.readLine();
 6         int n = Integer.parseInt(line);
 7         int res = dfs(n, Integer.MAX_VALUE, 0, 0);
 8         if(res == Integer.MAX_VALUE) {
 9             res = -1;
10         }
11         System.out.println(res);
12     }
13     private static int dfs(int n, int res, int cnt, int sum) {
14         if(sum == n) {
15             if(cnt < res) {
16                 res = cnt;
17             }
18             return res;
19         }
20         else if(sum > n) {
21             return res;
22         }
23         sum += 6;
24         res = dfs(n, res, cnt + 1, sum);
25         sum -= 6;
26         sum += 8;
27         res = dfs(n, res, cnt + 1, sum);
28         sum -= 8;
29         return res;
30     }
31 
32 }

View Code

讨论区：https://www.nowcoder.com/questionTerminal/61cfbb2e62104bc8aa3da5d44d38a6ef

类似题：https://www.nowcoder.com/question/next?pid=9439037&qid=36300&tid=14114220