Links from class:
Today there were two problems presented in class using Top-Down DP. The problem statements and solutions are below.
Wedding Shopping
Full problem statement. Abridged: You are going shopping for a wedding. There are C kinds of garments, of which there are K kinds of those garments. You have a budget of M. Buy one type of each garment so that the cost of the garments is maximized. (0 < C, K <= 20; 0 < M <= 200)
The solution below uses a recursive complete search with DP memoization. The states of the search are (money remaining, garment index), each of which has an optimal solution that is used to build into larger solution.
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
public class Main11450WeddingShoppingTopDown {
public static void main(String[] args) throws Exception {
new Main11450WeddingShoppingTopDown().run();
}
int memo[][] = new int[210][30];
int price[][] = new int[30][30];
int M, C;
public int solve(int money, int idx) {
if (money < 0) {
return -1;
} else if (idx == C) {
return M - money;
} else if (memo[money][idx] >= 0) {
return memo[money][idx];
} else {
int res = -1;
for (int i = 0; i < 20 && price[idx][i] >= 0; i++) {
res = Math.max(res, solve(money - price[idx][i], idx+1));
}
return memo[money][idx] = res;
}
}
public void run() throws Exception {
Scanner in = new Scanner(new InputStreamReader(System.in));
int N = in.nextInt();
while (N-- > 0) {
for (int[] m : memo) Arrays.fill(m, -1);
for (int[] p : price) Arrays.fill(p, -1);
M = in.nextInt();
C = in.nextInt();
for (int i = 0; i < C; i++) {
int K = in.nextInt();
for (int j = 0; j < K; j++) {
price[i][j] = in.nextInt();
}
}
int res = solve(M, 0);
if (res < 0) {
System.out.println("no solution");
} else {
System.out.println(res);
}
}
}
}
Flight Planner
Full problem statement. Abridged: Find the amount of fuel to spend on a flight from (0, 0) to (dist, 0). You are given a 10 unit tall wind map; tail winds reduce fuel and head winds increase fuel by the strength of the wind. You can decide to sink altitude by 1, climb altitude by 1, or hold altitude. Sinking costs 20 units, climbing costs 60 units, and holding costs 30 units.
The solution is a complete search using memoized DP. For each location, the plane may either hold, sink, or climb. Try each of these movements, and there will be lots of overlapping states. The function fuel(d, h) is the minimum amount of fuel required to from (d, h) to (D, 0) – where D is total flight distance.
import java.util.Arrays;
import java.util.Scanner;
// 10337 - Flight Planner
public class Main10337FlightPlanner {
public static void main(String[] args) throws Exception {
new Main10337FlightPlanner().run();
}
int windMap[][] = new int[1010][10];
int memo[][] = new int[1010][10];
int dist;
public int fuel(int d, int h) {
if (d == dist && h == 0) {
return 0;
} else if (h < 0 || h > 9 || d >= dist) {
return 1 << 20; // A very large value
} else if (memo[d][h] >= 0) {
return memo[d][h];
} else {
int res = fuel(d+1, h+1) + 60 - windMap[d][h];
res = Math.min(res, fuel(d+1, h) + 30 - windMap[d][h]);
res = Math.min(res, fuel(d+1, h-1) + 20 - windMap[d][h]);
return memo[d][h] = res;
}
}
public void run() throws Exception {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
while (N-- > 0) {
dist = in.nextInt() / 100;
for (int h = 9; h >= 0; h--) {
for (int d = 0; d < dist; d++) {
windMap[d][h] = in.nextInt();
}
}
for (int[] m : memo) Arrays.fill(m, -1);
System.out.println(fuel(0, 0));
System.out.println();
}
}
}
For next class
Assigned readings:
- Read section 3.5
Assigned problems:
- Midterm assignment