Creating a Maximal Configuration with Dynamic Programming

Question

I have been having some struggles trying to solve this problem I put below. I have a few ideas that I have tried. I first though of choosing all combinations of the N tuples and ordering them but the implementation was ugly and it was to slow. I think there is a dynamic programming approach to this problem. I am having trouble on how to create the configurations. After that, I think I know how to solve the problem.

Problem Statement:

Given a height H (1 <= H <= 1,000,000,000) we need to find a sequence of heights from N tuples that is greater than or equal to H. There are a few conditions: Each of the N tuples has a weight, height, and strength. A tuple's strength indicates the maximum amount of total weight that can be on top of that tuple.

The question asks to find the maximum safety value of the stack. The safety value is the amount of weight that can be added without exceeding any of the lower tuple's strength. If it is not possible, just print out -1.

INPUT:

The first line of input contains N and H.

The next N lines of input each describe a tuple, giving its height, weight, and strength. All are positive integers at most 1 billion.

SAMPLE INPUT:

4 10

9 4 1

3 3 5

5 5 10

4 4 5

SAMPLE OUTPUT:

2

Answer 1

Well, since no one else has posted a solution, I'll take a crack at it.

Given two tuples, t1 = (h1, w1, s1) and t2 = (h2, w2, s2), we can combine them as either
[t1 over t2] or [t2 over t1]. In each case, we can treat the result as another tuple; for example,

t3 = [t1 over t2] = (h1 + h2, w1 + w2, min(s1, s2 - w1))

(the resulting tuple's strength cannot be higher than either of the two strengths of the component tuples, and the strength of the bottom tuple is reduced by the weight of the tuple on top of it; the resulting strength can be negative).

Regardless of the order of composition, the resulting tuple's height and weight are the same; however, the resulting strength can differ depending on order. We're interested in tuples of maximum strength, so we take the max of the two possible values. Given the above, let's define composition as

t1 + t2 = (h1 + h2, w1 + w2, max(min(s1, s2 - w1), min(s2, s1 - w2)))

Resulting tuples can in turn be composed with other tuples, and so on.

What we need is to find the maximum strength out of all resulting tuples of height at least H, since the maximum safety value requested in the question is actually the strength of the resulting tuple.

So, we can set the starting max strength at -1, start composing tuples and, whenever we find one of height H or more, update the current max strength if the tuple's strength is larger.

Rule 1: A resulting tuple's strength cannot be higher than either of the two strengths of the component tuples, so, while composing tuples, whenever we find one of strength less than or equal to the current max, we can discard it, since no tuple in which it will be a component can have a strength higher than the current max.

Rule 1a: We can even discard the tuple that was used to update the current max strength, since the question doesn't ask us for the tuple itself, just the max value, and that tuple won't generate any better maximums in any other combination.

Rule 2: Now, let's take a top-down look. Any stack of n = 2k tuples can be seen as composed of two tuples, each composed of a stack of k tuples; for n = 2k + 1, the two stacks are of size k and k + 1.

So we build, in order:

1. the list of initial tuples;
2. the list of tuples resulting from stacks of two;
3. the list of tuples resulting from stacks of three, with tuples composed by taking one tuple from list [1] and one tuple from list [2] (all combinations, excluding the ones that use a primary tuple twice);
4. the list of tuples resulting from stacks of four, with tuples composed by taking two tuples, both from list [2] (again, all combinations, excluding the ones that use a primary tuple twice);

and so on, up to N. When building each list, we prune it according to rule 1 above.

Rule 1b: Whenever the max strength is updated, all existing lists should be pruned of tuples that have a strength less than or equal to the new max. This can be done either immediately, or lazily, whenever those tuples are encountered as part of composing new tuples.

As far as the description of the algorithm goes, I think this is it.

In terms of implementation, I'd store the actual tuples as std::tuple or a struct, with a twist: for each resulting tuple, you need to store the list of primary tuples it was built from; I'd use a std::vector<std::size_t> for that (containing the indexes of the primary tuples from the first list), as you can then use std::find_first_of to exclude combinations that use a primary tuple twice, or even better, if you keep the lists sorted, std::set_intersection.

For the lists at each level, std::vector as well.

The actual C++ code is, of course, your job.

---

Note: The algorithm described here has very bad worst-case complexity characteristics. Worst-case for this solution means: large N, large H, small tuple heights compared to H, small tuple weights compared to their strengths. In such a scenario, none of the pruning described in the rules above can kick in until very late, and until that happens we have combinatorial explosion.

However, for what I see as more 'interesting' cases, with more uniform distributions of heights, weights and strengths (similar to the example given), I think this solution would fare pretty well, even compared to a classical dynamic programming solution, which, in this case, would probably be something along the lines of the integer knapsack solution with one condition inverted (haven't really thought it out).

I may come back to this later on, when I'll have time to do some actual measurements, just out of curiosity.