[数据结构与算法]每日一题 --- 试题 历届真题 5个砝码【第二届】【省赛】【高职组】[蓝桥][Java]

题目：

资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
　　用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。
　　如果只有5个砝码，重量分别是1，3，9，27，81。则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。
　　本题目要求编程实现：对用户给定的重量，给出砝码组合方案。
输入输出用例
　　例如：
　　用户输入：
　　5
　　程序输出：
　　9-3-1
　　用户输入：
　　19
　　程序输出：
　　27-9+1
数据规模和约定
　　要求程序输出的组合总是大数在前小数在后。
　　可以假设用户的输入的数字符合范围1~121。

解题代码：

import java.util.Scanner;

public class 五个砝码 {
	public static void main(String[] args) {
		int[] arr = {81,27,9,3,1};
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] jilu = new int[5];
		boolean[] b = new boolean[5];
		f(n,arr,jilu,b, 0, 0);
	}
//	n 是要凑齐的数
//	arr是砝码组
//	jilu 是记录选中的砝码
//	k 是要操作的砝码数
//	b 记录加减
	public static void f(int n, int[] arr,int[] jilu,boolean[] b,int k,int in) {
//		出口
		if (n == 0) {
			for (int i = 0; i < in; i++) {
				if (b[i]) {
					if (i == 0) {
						System.out.print( jilu[i]);
						continue;
					}
					System.out.print( "+" + jilu[i]);
				}else {
					System.out.print( "-" + jilu[i]);
				}
			}
			System.out.println();
			return;
		}
		if (k >= arr.length) {
			return;
		}
		
//		使用 + 
//		尝试
		n -= arr[k];
		jilu[in] = arr[k];
		b[in] = true;
		f(n, arr, jilu, b, k + 1, in + 1);
//		回溯
		n += arr[k];
		jilu[in] = 0;
		b[in] = false;
//		使用 -
//      尝试
		n += arr[k];
		jilu[in] = arr[k];
		f(n, arr, jilu, b, k + 1, in + 1);
//	回溯
		n -= arr[k];
		jilu[in] = 0;
//		不使用
		f(n, arr, jilu, b, k + 1, in);
	}
}

这个题可以使用递归也可以使用循环，因为只有五层，对速度影响不大。