Tallest tower from a set of digits

Question

Edit: Bounty puzzle at the end of the question.

Given a set of 1-digit numbers, you should determine how tall a tower they can construct.

The digits live on a horizontal plane with a ground level where they can stand. No digit wants to be confused with a multi-digit number, so they always have an empty space on both of their sides.

4 2  1 9  6  8

A digit can be on top of another one:

2
6

or can be supported by two other diagonally below it:

 9
5 8

The bottom one(s) have to support the weight the upper one supports (if there is any), plus the upper one's weight which is always 1. If there are two supporters, they split the upper one's total weight evenly (50%-50%).

The weight of every digit is 1 independent of it's value.

If one digit supports two others it has to be able to support the sum of their corresponding weight. A digit can support at most its numerical value.

Some valid towers (with heights 4, 3 and 5):

            0          
7           1
5    1     1 1         9 supports a total weight of 1.5 = (1+1/2)/2 + (1+1/2)/2
2   5 4    5 5        
3  5 9 5  5 6 3        6 supports a total weight of 3 =  1.5 + 1.5 = (2*1+(2*1/2))/2 + (2*1+(2*1/2))/2

Some invalid towers:

1         5           The problems with the towers are (from left to right):
1  12    2 3     8      1 can't support 1+1; no space between 1 and 2;
1  5 6  1 1 1   9       1 can't support 1.5 = (1+1/2)/2 + (1+1/2)/2; 8 isn't properly supported (digits at both bottom diagonals or exactly below the 8)    

You should write a program or function which given a list of digits as input outputs or returns the height of the highest tower constructable by using some (maybe all) of those digit.

Input

• A list of non-negative single-digit numbers with at least one element.

Output

• A single positive integer, the height of the highest constructable tower.
• Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).

Examples

Format is Input list => Output number with a possible tower on the next lines which is not part of the output.

[0]  =>  1

0

[0, 1, 1, 1, 1, 1]  =>  3

  0
  1
 1 1

[1, 1, 1, 1, 1, 2, 2]  =>  4

   1
   1
  1 1
 1 2 2

[0, 0, 2, 2, 2, 2, 2, 5, 5, 5, 7, 7, 9]  =>  9

0
2
2
5
5
5
7
7
9

[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5]  =>  9

   1
   2
   2
   3
   4
   5
  3 3
 4 4 4
5 5 5 5

[0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 9]  =>  11

   0
   1
   2
   3
   4
   5
  3 3
  4 5
  5 5
 3 7 3
2 7 9 2

[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]  =>  12

 0
 1
 2
 3
 4
 5
 6
 7
4 5
6 7
8 8
9 9

[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9]  =>  18

      0
      1
      2
      3
      4
      5
      6
      7
      8
      9
     5 5
     6 6
     7 7
    4 8 4
   3 7 7 3
  2 6 8 6 2
 2 5 8 8 5 2
 3 9 9 9 9 3

This is code-golf, so the shortest entry wins.

Bounty

I will award 100 reputation bounty (unrelated to the already awarded one) for solving the extended problem below in polynomial time (in regard to the length of the input list) or proving that it isn't possible (assuming P!=NP). Details of the extended problem:

• input numbers can be any non-negative integers not just digits
• multi-digit numbers take up take same place as single-digit numbers
• multi-digit numbers can support they numerical value e.g. 24 can support 24

The bounty offer has no expiry date. I will add and reward the bounty if a proof appears.

Answer 1

Python 2 - 326

Runs easily under the time limit for all the examples given, though I did sacrifice some efficiency for size, which would probably be noticeable given much larger inputs. Now that I think about it though, since only single digits numbers are allowed the largest possible tower may not be very big, and I wonder what the maximum is.

def S(u,c=0,w=[]):
 for(s,e)in[(len(w),lambda w,i:w[i]),(len(w)+1,lambda w,i:.5*sum(([0]+w+[0])[i:i+2]))]:
    m=u[:];l=[-1]*s
    for n in u:
     for i in range(s):
        if 0>l[i]and n>=e(w,i):m.remove(n);l[i]=n;break
    if([]==l or-1in l)==0:
     for r in S(m,c+1,[1+e(w,i)for i in range(s)]):yield r
 yield c
print max(S(sorted(input())))