360校招前端第一题

题目

小明一共有n根彩色粉笔，m根白色粉笔，现在可以用a根彩色粉笔盒b根白色粉笔组成一盒卖x元，或者c根白色粉笔组成一盒卖y元，或者d根彩色粉笔组成一盒卖z元，小明最多可以用这些粉笔卖多少元？不一定要将所有的粉笔卖完，小明只希望利益最大化。

输入
第一行2个整数n,m
第二行4个整数a,b,c,d
第三行3个整数x,y,z
输出
输出一行整数，表示最多可以卖到多少元
样例输入
5 5
1 2 3 3
2 1 3
样例输出
7

题意

背包问题，没有用DP解，给出通项公式：
diGui(n,m,res,pre)=max(diGui(n-a,m-b,res,pre) ,diGui(n-d,m,res,pre) ,diGui(n,m-c,res,pre) )
对于每次n，m都有三次选择，在三次选择后的结果中找出最大的返回

Java实现

 public static int diGui(int n, int m, int a, int b, int c, int d, int x, int y, int z, int result, int pre) {
	int out1, out2, out3, out;
	if (n >=0 && m >= 0) {
		out1 = result;
		out2 = result;
		out3 = result;
		out = result;
		if (n - a >= 0 && m - b >= 0) {
			out1 = diGui(n - a, m - b, a, b, c, d, x, y, z, result + x, x);
		}
		if (n - d >= 0) {
			out2 = diGui(n - d, m, a, b, c, d, x, y, z, result + z, z);
		}
		if (m - c >= 0) {
			out3 = diGui(n, m - c, a, b, c, d, x, y, z, result + y, y);
		}
		if (out1 > out2 && out1 > out3) {
			out = out1;
		}
		if (out2 > out1 && out2 > out3) {
			out = out2;
		}
		if (out3 > out2 && out3 > out1) {
			out = out3;
		}
		return out;
	}else{
		return result-pre;
	}
	
}

public static void getMax() {
	int n, m;
	int a, b, c, d;
	int x, y, z;
	int result;
	// 读取输入
	Scanner scanner = new Scanner(System.in);
	n = scanner.nextInt();
	m = scanner.nextInt();
	a = scanner.nextInt();
	b = scanner.nextInt();
	c = scanner.nextInt();
	d = scanner.nextInt();
	x = scanner.nextInt();
	y = scanner.nextInt();
	z = scanner.nextInt();
	scanner.close();

	result = diGui(m, n, a, b, c, d, x, y, z, 0, 0);
	System.out.println(result);
}