首页 > 试题广场 >

买苹果

[编程题]买苹果
  • 热度指数：28595 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。

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


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

输入

20

输出

3
算法知识视频讲解
添加回答
C/C++
人生就是这样啊头像 人生就是这样啊 
/*
   本题采用的更一般的DP方法，和前面的跳石阶思路一样。
*/
#include <iostream>  
#include <vector> 
#include <algorithm>
using namespace std;

#define INT_MAX 100
vector<int> num = { 6, 8 };
int n;

int solution(vector<int> state){
	for (int i = 0; i < state.size(); i++){
		if (state[i] == INT_MAX)
			continue;
		for (int j = 0; j < num.size(); j++){
			if (i + num[j] <= n){
				state[i + num[j]] = min(state[i + num[j]], state[i] + 1);
			}
		}
	}
	return state[n] == INT_MAX ? -1 : state[n];
}

int main()
{  
	cin >> n;
	vector<int> state(n + 1, INT_MAX);
	state[0] = 0;
	cout << solution(state)<< endl;
	cin.get();
	cin.get();
	return 0;
}

发表于 2017-03-28 19:41:16 回复(1)
juding头像 juding 
// 思路：
// 要想袋数尽量少，也就是8个每袋的越多越好。
// 当n<=5时，不能购买，输出-1；
// 当n>6时：
// 如果n可以被8整除（n%8==0），则袋数为n/8；
// 如果n为奇数，则不存在。（因为8和6乘上某个数相加肯定为偶数）
// 如果n除8余下一个偶数，则袋数为n/8+1。（肯定可以通过增加6的袋数和减少8的袋数来得到想要的值（不断减少2））

import java.util.Scanner;
public class Main {	
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		// 小于6的值
		if(n<=5){
			System.out.println(-1);
		}
		// 其他
		if(n%8==0){
			System.out.println(n/8);
		}else if((n%8)%2==0&&n!=10){
				System.out.println(n/8+1);
		}else{  
				System.out.println(-1);
		}	
	}
}

编辑于 2017-08-10 15:27:29 回复(2)
Python
华科平凡头像 华科平凡

python 解法：

这道题还用什么动态规划啊。直接暴力求解多省事

def calcMinimumBags(number):
    for i in range(number // 6 + 1):
        if (number - i * 6) % 8 == 0:
            return i + (number - i * 6) // 8
    return -1
print(calcMinimumBags(int(input())))
发表于 2018-04-12 16:07:22 回复(3)
小渣渣渣渣渣渣头像 小渣渣渣渣渣渣
n=int(input())
q=0
whilen>24:
    n-=8
    q+=1
ifn==24orn==18orn==20orn==22:
    print(q+3)
elifn==12orn==16orn==14:
    print(q+2)
elifn==6orn==8:
    print(q+1)
else:
    print("-1")
#人工想出了这些情况，属于钻了个空子吧，不比那些大神的算法
发表于 2017-12-18 19:20:04 回复(1)
邓丽璇头像 邓丽璇 
import java.util.Scanner;
public class main{
    public static void main(String []args){
        Scanner s = new Scanner(System.in);
            while(s.hasNext()){
             int n = s.nextInt();
             int count = n/6;
             boolean flag = true;
             int i,j;
             for(i = 0;i <= n / 6;i++){
                 for(j = 0;j <= n / 8;j++){
                     if(6 * i + 8 * j == n){
                         count = Math.min(count,i + j);
                         flag = false;
                     }
                 }
             }
             if(flag){
                 count = -1;
             }
             System.out.print(count);
         }
    }
}

编辑于 2017-09-27 21:41:39 回复(0)
Java
牛客9031555号头像 牛客9031555号 
package test20180826;

import java.util.Scanner;


/*
感觉我这个思路蛮简单，首先是看可以对8整除不，
如果不能在看可以选出几个8和6组合，
8的个数从app/8到0个变化，取相应的6的个数。
如果上边取不到整数，就相当于不可行。
我前后使用了一个标记，boo,如果取到整数了
就是true，否则是false,
*/
public class Main2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        boolean boo = false;
        while (sc.hasNext()) {
            int app = sc.nextInt();
            if (app % 8 == 0) {
                System.out.println(app / 8);
                boo = true;
            } else {
                for (int i = app / 8; i >= 0; i--) {
                    if ((app - i * 8) % 6 == 0) {
                        System.out.println(i + (app - i * 8) / 6);
                        boo = true;
                        break;
                    }
                }
                if (boo == false) {
                    System.out.println(-1);
                }
            }
        }
    }
}

编辑于 2018-08-26 10:48:45 回复(1)
牵着蜗牛头像 牵着蜗牛 
import java.util.Scanner;
public class Main{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        System.out.println(check(num));
        
    }
    public static int check(int num){
        for(int i=0;i<=num/6;i++){
            int remain=num-i*6;
            if(remain%8==0){
                return i+remain/8;
            }
        }
        return -1;
        
    }
}

编辑于 2018-05-31 17:23:22 回复(0)
C/C++
wollir头像 wollir
//借鉴题目跳石板的大佬解法（动态规划）
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> dp(n + 1, INT_MAX);
    dp[6] = 1;    dp[8] = 1;
    for (int i = 12; i <= n; i+=2) {
        if (dp[i - 6] != INT_MAX && dp[i] > dp[i - 6] + 1)
            dp[i] = dp[i - 6] + 1;
        if (dp[i - 8] != INT_MAX && dp[i] > dp[i - 8] + 1)
            dp[i] = dp[i - 8] + 1;
    }
    cout << ((dp[n] == INT_MAX) ? -1 : dp[n]);
    return 0;
}
发表于 2018-05-22 17:39:10 回复(0)
labulaka520头像 labulaka520

四行

num = int(input())
if num % 2 != 0:print("-1")
elif num %8 == 0:print(num//8)
else:print(num//8 - 1 + (num % 8 + 8)//6)
发表于 2017-09-02 12:26:16 回复(2)
Python
Traveling Light头像 Traveling Light 
if __name__ == "__main__":
    a = raw_input()
    a = int(a)
    min_ = 100
    times = 0
    for i in range(a / 8 + 1):
        rest = a - i * 8            
        if(rest % 6 == 0):
            times = i + rest /6
            min_ = min(times,min_)
    if min_ == 100:
        print -1
    else:
        print min_
稍做分析发现 6 和 8比较特殊，大于10的偶数都能够满足要求
编辑于 2016-09-25 17:13:08 回复(0)
我就是大蹭蹭头像 我就是大蹭蹭 
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] bags = new int[n+1];
        Arrays.fill(bags, Integer.MAX_VALUE);
        bags[0] = 0;
        for(int i=0; i<=n;i++){
            if(bags[i] == Integer.MAX_VALUE)
                continue;
            if(i+8 <= n)
                bags[i+8] = Math.min(bags[i+8], bags[i]+1);
            if(i+6 <= n)
                bags[i+6] = Math.min(bags[i+6], bags[i]+1);
        }
        if(bags[n] == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(bags[n]);
    }
}

发表于 2018-02-25 20:35:24 回复(0)
美团到店招聘头像 美团到店招聘 
#include <stdio.h>
#include <iostream>
#include "math.h"
using namespace std;
 
int main(){
    int n;
    scanf("%d",&n);
    int count = 0;
    while(n>=8){
        n -= 8;
        count++;
    }
    if(n == 6 || (n == 4 && count >=1) || (n == 2 && count >=2))
        count++;
    else
        if(n == 0)
            count = count;
        else
            count = -1;
    printf("%d",count);
     
}

发表于 2017-02-08 19:26:37 回复(0)
AlgorithmM头像 AlgorithmM 
#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<=n/6;i++){
        if((n-6*i)%8==0){
            cout << (i+ (n-6*i)/8);
            return 0;
        }
    }
    cout<<-1<<endl;
    return 0;
}

发表于 2016-11-16 21:02:27 回复(0)
C/C++
~accelerator();头像 ~accelerator(); 
#include<stdio.h>
int main()
{
    double a,b;
    int n,i;
    scanf("%d",&n);
    for(i=12;i>=0;--i,--a){
        a = (double)i;
        b = ((double)n - 8*a)/6;
        if(b - (int)b == 0 && b >= 0){
            printf("%d",(int)(b+a));
            break;
        }
    }
    if (!(b - (int)b == 0 && b >= 0))
        printf("-1");
}

发表于 2020-01-09 10:40:05 回复(1)
咖啡糖66头像 咖啡糖66 
/**

思路：4袋 六个装 的 == 3袋 八个装 的。
为了尽可能少袋子，因此 六个装的只可能 0 1 2 3 这几种情况。
尝试这四种情况下的总袋数最少的情况
*/

#include <iostream>

using namespace std;

int main()
{
    int n;
    while(cin>>n){
        int res = 999999;
        for(int i=0;i<=3;i++){ //六个一袋  的袋数
            int remain = n - i*6; //remain表示要装到  八个每袋  的苹果数量。
            if(remain%8!=0) continue;
            else{
                if( (i+remain/8)<res ){
                    res = i+remain/8;
                }
            }
        }
        if(res == 999999){
            cout<<-1<<endl;
        }else{
            cout<<res<<endl;
        }
    }
    return 0;
}

发表于 2019-08-31 01:34:54 回复(0)
Yumho头像 Yumho

BFS + visited
其实 实质和DP是一样的

n = int(input())

def solve():
    level = [n]
    path = 1
    visited = set()
    while level:
        temp = set()
        for l in level:
            a = l - 6
            b = l - 8
            if a == 0:
                return path
            if b == 0:
                return path
            if a > 0 and a not in visited:
                temp.add(a)
                visited.add(a)
            if b > 0 and b not in visited:
                temp.add(b)
                visited.add(b)
        level = temp
        path += 1
    return -1

print(solve())
发表于 2019-08-02 21:31:41 回复(0)
Python
DJy201807201027569头像 DJy201807201027569
完全不用DP这么复杂的，因为题目最大数只有100所以直接找出所有100以内符合的数做对应的最小的组合数即可。
1，如果全用6或者8即最多17*6和13*8，所以循环17个6与13个8进行组合
2，定义字典res{}，K为复合要求的苹果总数，V为此K下最小的组合数，发现res中K已经存在则判断当前下的V与之前存储的V取最小值更新，否则直接存储
3，输出先判断是否在K中，再直接输出对应的V，否则输出-1即可 

import sys
N=int(input())
res={}
for i in range(0,17):
    for j in range(0,13):
        a=i*6+j*8
        if(1<=a<=100):
            if(a)in res.keys():res[a]=min(res[a],i+j)
            else:res[a]=i+j
if N in res.keys():print(res[N])
else:print(-1)


发表于 2018-08-26 10:57:36 回复(0)
C/C++
一个好听的名字头像 一个好听的名字 
/* BFS六八选项，找到合适跳出 */
#include <iostream>
#include <queue>
using namespace std;
struct node
{
    int x;
    int dai;
};
void BFS(int n)
{
    queue<node> que;
    node temp;
    temp.x = 6;
    temp.dai = 1;
    que.push(temp);
    temp.x = 8;
    que.push(temp);
    while(!que.empty())
    {
        temp = que.front();
        que.pop();
        if (temp.x == n)
        {
            cout << temp.dai;
            return;
        }
        temp.dai++;
        temp.x += 6;
        if (temp.x <= n)
        {
            que.push(temp);
        }
        temp.x += 2;
        if (temp.x <= n)
        {
            que.push(temp);
        }
    }
    cout << -1;
    return; 
}
int main()
{
    int n = 0;
    cin >> n;
    BFS(n);
    return 0;
}

发表于 2018-08-15 19:34:51 回复(0)
Python
半夏半暖头像 半夏半暖
n = int(input())
result = []
for i in range(n//8+1):
    for j in range(n//6+1):
        if 8*i + 6*j == n:
            result.append(i+j)
if len(result) == 0:
    print(-1)
else:
    print(min(result))

发表于 2018-07-31 11:51:55 回复(0)
C/C++
鸟生魚汤头像 鸟生魚汤 
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n<6)cout<<-1;
    if(n==6)cout<<1;
    if(n==7)cout<<-1;
    if(n==8)cout<<1;
    if(n<=8)return 0;
    vector<int> v(n+1,999);
    v[6]=1;
    v[8]=1;
    for(int i=9;i<=n;i++){
        v[i]=min(v[i-6],v[i-8])+1;//关键,从下往上
    }
    if(v[n]>900)cout<<-1;
    else cout<<v[n];
    return 0;
}

编辑于 2018-07-24 00:06:37 回复(0)
提交观点

问题信息

贪心 动态规划 数学
来自：网易2017秋招编程题集合
难度：
246条回答 26038浏览

热门推荐

通过挑战的用户

查看代码

相关试题

买苹果

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号