2022.09.21-秋招-年会奖品分配策略

TaZi SU @ 7 months ago

题目大意

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

题目思路

分配方式：

每个奖品只能被分配到一个奖项中。每个奖项至少分配一个奖品，以确保 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);
});

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

# Submissions

169

Accepted

Uploaded By

TaZi

1 solutions

题目大意

题目思路

代码

Information

Status

Development

Support