分析

• 思路1：动态规划（通用解法）

采用动态规划求解。思路同本文中前面的编程题——跳石板。创建一个vector容器steps，steps[i]表示购买i个苹果所需的最小袋数。初始化为steps容器为INT_MAX。从1苹果开始遍历，若steps[i]为INT_MAX，表示无法购买该个数的苹果，直接开始下次循环。若steps[i]不为INT_MAX，表示该个数的苹果可以购买，进行动态规划求解。动态规划的转移方程为

steps[i+j] = min(steps[i]+1,steps[i+j])   //j为6或8
steps[0] = 0

动态规划的过程如下图所示。

• 思路2：贪婪算法

对于金额，优先选取每袋含有8个苹果的包装。若还有余数，则再用6个装的包装去购买。如果不行的话，则将8个装的个数减去1个，进行回溯，再用6包装的去购买。如果还不行的话，再次回溯，直到购买8包装的个数为0。

贪婪算法并不一定能得到最优解，但是一个可行的，较好的解。下面对使用贪婪算法能否得到最优解进行分析。

首先，6和8都是偶数。因此，能凑出的个数也一定是偶数。程序中若苹果总数是奇数，可以直接返回-1。

再次，偶数个苹果数对8取模，其结果只可能为0,2,4,6。若余数为6或者0，则可以直接用6包装情况处理，不需要回溯购买8包装的情况。若余数为4，只需回溯1次即可，因为8+4=12, 12%6 = 0。若余数为2，只需回溯2次即可，因为8+8+2=18, 18%6 = 0。

综上，本题情况使用贪婪算法一定能得到最优解。

贪婪算法并不一定能得到最优解，但是一个可行的，较好的解。例如，给定硬币coins=[1,2,10,25]，金额总数amounts=30，不限制每种币值的硬币数量，要求用所给硬币凑出所需金额，并且硬币数量最少。若采用贪婪算法求解，需要6枚（25+5*1）硬币。 若采用动态规划求解，所需3枚（10+10+10）硬币。 --- 贪婪算法

• 思路3：数字分析求解。O(1)算法

对数字特征进行分析。

首先，6和8都是偶数。因此，能凑出的个数也一定是偶数。程序中若苹果总数是奇数，可以直接返回-1。

再次，偶数个苹果数对8取模，其结果只可能为0,2,4,6。若余数为6或者0，则可以直接用6包装情况处理，不需要回溯购买8包装的情况。若余数为4，只需回溯1次即可，因为8+4=12, 12%6 = 0。若余数为2，只需回溯2次即可，因为8+8+2=18, 18%6 = 0。

综上，可以采用如下思路进行处理。（由于数字6和8的特征，本方法只适用于本题）

• 情况1：若num不是偶数，则直接返回-1
• 情况2：若num%8 = 0，则返回num/8
• 情况3：若num%8 != 0，则只需回溯1次或者2次8包装购买个数，就可以求解。回溯1次，其结果为n/8-1+2 = n/8+1；回溯1次，其结果为n/8-2+3 = n/8+1。因此，可以情况3下，可以返回n/8+1。

求解

• 方法1：动态规划。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main(){
    int amounts;
    cin>>amounts;
    vector<int> steps(amounts+1,INT_MAX);
    steps[6] = 1;
    steps[8] = 1;
    for(int i=6;i<=amounts;i++){
        if(steps[i] == INT_MAX){
            continue;
        }
        else{
            if(i+6 <= amounts){
                steps[i+6] = min(steps[i]+1,steps[i+6]);
            }
            if(i+8 <= amounts){
                steps[i+8] = min(steps[i]+1,steps[i+8]);
            }

        }
    }
    steps[amounts] = (steps[amounts] == INT_MAX)? -1:steps[amounts];

    cout<<steps[amounts]<<endl;
    return 0;
}

• 方法2：贪婪算法。

#include <iostream>
using namespace std;

int maxPackages(int num) {
    int res = 0;
    int mul, remains;
    if(num%2 != 0){
        return -1;  //非偶数直接返回
    }

    if (num % 8 == 0) {
        res += num / 8;
        return res;
    }
    else{
        mul = num / 8;  //倍数
        remains = num % 8;
        res += mul;
        num = num % 8;
        while (mul >= 0) {  //回溯8包装
            if (num % 6 == 0) {
                res += num / 6;
                return res;
            }
            else {
                mul--;  //回溯  8包装购买袋数-1
                res--;
                num = num + 8;
            }
        }
    }
    return -1;

}


int main() {
    int num;
    while (cin >> num) {
        cout << maxPackages(num) << endl;
    }
    return 0;
}

• 方法3：数字分析求解。O(1)。

#include <iostream>
using namespace std;

int main() {
    int num;
    while (cin >> num) {
        if(num%2 != 0){
            cout<<-1<<endl;
        }
        else{
            if(num%8 == 0){
                cout<<num/8<<endl;
            }
            else{
                cout<<1+num/8<<endl;
            }
        }
    }
    return 0;
}

/*
   本题采用的更一般的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;
}

// 思路：
// 要想袋数尽量少，也就是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);
		}	
	}
}

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())))

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);
         }
    }
}

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);
                }
            }
        }
    }
}

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;
        
    }
}

四行

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)

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_

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]);
    }
}

	

#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);
     
}

#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;
}

#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");
}

/**

思路：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;
}

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())

/* 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;
}

#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;
}