题目大意

这道题目要求将若干个奖品分配到三个不同的奖项（一等奖、二等奖、三等奖）中，使得一等奖的总价格大于二等奖，二等奖的总价格大于三等奖，同时尽可能地减小一等奖和三等奖之间的价格差异

题目思路

分配方式：

每个奖品只能被分配到一个奖项中。 每个奖项至少分配一个奖品，以确保 x, y, z 都大于零。

搜索策略：

由于奖品数量 n 在 [3, 16) 的范围内，可以考虑使用深度优先搜索（DFS）或回溯算法来穷举所有可能的分配方案。 每个奖品有三种选择（分配到一等奖、二等奖或三等奖），因此总的分配方式为 3^n。当 n 较小时（如 n=15），这种方法是可行的，尤其是通过优化剪枝来减少实际的计算量。

剪枝策略：

早期终止：在分配过程中，如果当前的分配方案已经无法满足 x > y > z 的条件，可以立即终止该分支的搜索。 排序：将奖品按价格从大到小排序，优先分配价格较高的奖品，有助于更快地达到 x > y > z 的条件，并可能触发更多的剪枝。 记录最小差值：在搜索过程中，维护一个全局变量记录当前找到的最小 x - z，并在搜索过程中不断更新。当当前路径的 x - z 已经不小于已记录的最小差值时，可以剪枝。 优化目标：

目标是最小化 x - z，因此在搜索过程中，可以优先考虑那些使 x - z 较小的分配方案。 通过维护一个全局最小差值，可以在搜索过程中不断更新，以确保最终得到最优解。

代码

Java代码

import java.util.Scanner;

public class Main {
    static int n;
    static int[] arr = new int[16];
    static int minn = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);//输入
        n = input.nextInt();
        for(int i = 1; i <= n; i++){
            arr[i] = input.nextInt();
        }
        dfs(1, 0, 0,0);
        if(minn == Integer.MIN_VALUE) System.out.println(0);//如果minn没更新过，说明没有合理的分法，那么就输出0
        else System.out.println(minn);

    }
    static void dfs(int tar, int sumx, int sumy, int sumz){
        if(tar == n + 1){//dfs终止条件
            if(sumx > sumy && sumy > sumz && sumz > 0){
                minn = Math.min(minn, sumx - sumz);
            }
            return;
        }//下面三个dfs分别表示第tar物品，放进哪个盒子
        dfs(tar + 1, sumx + arr[tar], sumy, sumz);
        dfs(tar + 1, sumx, sumy + arr[tar], sumz);
        dfs(tar + 1, sumx, sumy, sumz + arr[tar]);
    }
}

C++代码

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int arr[16];
int minn = 2e9;
void dfs(int tar, int sumx, int sumy, int sumz) {
	if (tar == n + 1) { //dfs终止条件
		if (sumx > sumy && sumy > sumz && sumz > 0) {
			minn = min(minn, sumx - sumz);
		}
		return;
	}//下面三个dfs分别表示第tar物品，放进哪个盒子
	dfs(tar + 1, sumx + arr[tar], sumy, sumz);
	dfs(tar + 1, sumx, sumy + arr[tar], sumz);
	dfs(tar + 1, sumx, sumy, sumz + arr[tar]);
}
int main() {
	cin>>n;
	for (int i = 1; i <= n; i++) {
		cin>>arr[i];
	}
	dfs(1, 0, 0, 0);
	if (minn == (int)2e9) cout<<0<<endl; //如果minn没更新过，说明没有合理的分法，那么就输出0
	else cout<<minn<<endl;
	return 0;
}

Python代码

def dfs(tar,sumx,sumy,sumz):
	global minn
	if (tar == n + 1):#dfs终止条件
		if (sumx > sumy and sumy > sumz and sumz > 0): 
			minn = min(minn, sumx - sumz);
		return;
	#下面三个dfs分别表示第tar物品，放进哪个盒子
	dfs(tar + 1, sumx + arr[tar], sumy, sumz);
	dfs(tar + 1, sumx, sumy + arr[tar], sumz);
	dfs(tar + 1, sumx, sumy, sumz + arr[tar]);

arr=[0 for i in range(16)]
minn = int(2e9);
n=int(input())
arr=list(map(int,input().split()))
arr.insert(0,0)
dfs(1,0,0,0)
if minn==int(2e9):#如果minn没更新过，说明没有合理的分法，那么就输出0
	print(0)
else:
	print(minn)

Js代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';

process.stdin.on('data', (data) => {
	input += data;
	return;
});
process.stdin.on('end', () => {
    function dfs(tar,sumx,sumy,sumz){
        if (tar == n + 1) { //dfs终止条件
            if (sumx > sumy && sumy > sumz && sumz > 0) {
                minn = Math.min(minn, sumx - sumz);
            }
            return;
	   }//下面三个dfs分别表示第tar物品，放进哪个盒子
        dfs(tar + 1, sumx + arr[tar], sumy, sumz);
        dfs(tar + 1, sumx, sumy + arr[tar], sumz);
        dfs(tar + 1, sumx, sumy, sumz + arr[tar]);
    }
    let minn = Number(2e9);
    input=input.split('\n');
    var n=Number(input[0][0]);
    var arr=new Array();
    for (let i=1;i<=n;i++)
        arr[i]=Number(input[1].split(' ')[i-1]);
    dfs(1, 0, 0, 0);
	if (minn == 2000000000) console.log(0); //如果minn没更新过，说明没有合理的分法，那么就输出0
	else console.log(minn);
});

题目内容

小明的公司准备在年会上开展抽奖活动。他们购买了若干个奖品，每个奖品都有一个价格，用一个正整数数组表示。在抽奖环节，公司准备设置一等奖、二等奖和三等奖，每个等级设置一个奖品，并将所有奖品分成三份大礼包。公司希望尽可能地减小一等奖和三等奖之间的价格差异，同时满足一等奖总价格大于二等奖总价格，二等奖总价格大于三等奖总价格。

为了实现这一目标，公司需要找到一种合适的分配方案。具体来说，假设一等奖总价格为 $x$，二等奖总价格为 $y$，三等奖总价格为 $z$，则 $x>y>z>0$。同时，假设奖品的总数量为 $n$，用正整数数组 $array$ 表示每个奖品的价格。

现在的问题是小明他们不知道如何分配奖品，才能使得一等奖和三等奖之间的价格差最小，你能帮帮他们吗？

输入描述

第一行：正整数 $n$ ，表示奖品的数量，取值范围 $[3,16)$

第二行：一个正整数数组 $array$ ，每个元素表示奖品的价格，取值范围 $[1,1000]$

输出描述

一个非负整数，表示一等奖和三等奖的差值，没有方案返回 $0$

样例

样例一：

输入

3
5 4 2

输出

3

样例解释

分配方案只有一种 ${5,4,2}$

样例二：

输入

4
10 5 4 2

输出

5

样例解释

分配方案有 ${10,9,2}$ ， ${10,7,4}$ ， ${10,6,5}$ ，${15,4,2}$ ， ${14,5,2}$ ， ${12,5,4}$

一等奖和三等奖差值最小的方案是 ${10,6,5}$