TCHS-4-1100

Problem Statement

Your master construction unit can build 1 unit of type 0 in times[0] seconds at a cost of costs[0]. Each unit of type 0, once built, can in turn build 1 unit of type 1 in times[1] seconds at a cost of costs[1]. Type 1 units can build units of type 2, and so forth. Let N denote the number of elements in times. Given totTime seconds, return the greatest number of units of type N-1 that can be created without exceeding a total cost of totCost.

Definition

Class:	ProductionOptimization
Method:	getMost
Parameters:	int[], int[], int, int
Returns:	int
Method signature:	int getMost(int[] costs, int[] times, int totCost, int totTime)
(be sure your method is public)

Constraints

-

costs will contain between 2 and 50 elements, inclusive.

-

times will contain the same number of elements as costs.

-

Each element of costs will be between 1 and 100, inclusive.

-

Each element of times will be between 1 and 100, inclusive.

-

totTime will be between 1 and 100, inclusive.

-

totCost will be between 1 and 100, inclusive.

Examples

0)

{1,1}

{1,1}

3

3

Returns: 2

Build 1 unit 0, and then 2 of unit 1.

1)

{1,1}

{1,1}

5

3

Returns: 3

Build 2 of unit 0. The first will be able to build 2 of unit 1. The second will be able to build 1.

2)

{ 1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1}

{ 1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1}

100

100

Returns: 51

A lot of unit types.

3)

{1, 1}

{3, 12}

100

27

Returns: 6

4)

{20,1}

{20,1}

17

19

Returns: 0

import java.util.Arrays;

public class ProductionOptimization {

	int[][][] dp = new int[64][128][128];
	int[] costs, times;

	int solve(int i, int c, int t) {
		if (dp[i][c][t] != -1)
			return dp[i][c][t];
		if (i == costs.length)
			return 1;
		int c2 = c - costs[i];
		int t2 = t - times[i];
		if (c2 < 0 || t2 < 0)
			return 0;
		int ret = 0;
		for (int k = 0; k <= c2; k++)
			ret = Math.max(ret, solve(i, k, t2) + solve(i + 1, c2 - k, t2));
		return dp[i][c][t] = ret;
	}

	public int getMost(int[] costs, int[] times, int C, int T) {
		this.costs = costs;
		this.times = times;
		for (int[][] a : dp)
			for (int[] b : a)
				Arrays.fill(b, -1);
		return solve(0, C, T);
	}

}