Mrrl

В вашем примере каждое из чисел, кроме 5, делится на предыдущее. Поэтому, до определённого момента - пока осталось заплатить не меньше 10 руб, и в кошельке есть купюры не меньше 10 - можно пользоваться "жадным" алгоритмом - брать самую большую купюру, которая меньше остатка стоимости товара.
Допустим, что остались только монеты по 1,2,5 руб. Если есть хотя бы одна монета 1 руб - то платить пятирублёвой монетой безопасно, даже если останется нечётная цена - то набрать её рублём и двушками удастся. Если есть две монеты по 5 руб, и осталось заплатить не меньше 10 - смело тратьте одну из них. Вторую тратить подождите, это может быть опасно.
В конце концов у вас останутся только пятачки и двушки, причём либо пятачков не более одного, либо осталось заплатить меньше десятки. Смотрите. Если надо заплатить нечётную сумму: если пятачков нет или надо заплатить 1 или 3 рубля - задача неразрешима. В противном случае тратите пятачок, остаётся чётная сумма.
Пытаетесь набрать остаток двушками. Если их хватило - вы победили. Если нет, то вам подсунули неразрешимый пример...
Если бы набор купюр и монет был из времён СССР (1,2,3,5,10,15,20,50,100,300,500,1000,2500,5000,10000), задача была бы значительно сложнее и интереснее.

UPD. Моё решение неверно. Кто найдёт контрпример?

Более правильный вариант.
- если есть хотя бы одна монета в 1 руб, то работает "жадный" алгоритм - в цикле платите самой большой купюрой, которая у вас есть и не превышает остатка суммы.
- если монеты 1 руб. нет:
- - если сумма, которую надо набрать, нечётна, а пятачка нет, вы проиграли.
- - если сумма, которую надо набрать, нечётна, и есть хотя бы один пятачок, вносим его. Переходим к следующему пункту.
- - если остаток суммы, который надо набрать, чётен - объединяем пятачки в пары (и по одному пятачку платить не будем, даже если хочется). И запускаем жадный алгоритм. Если задача разрешима, то он справится.

(Про исходную задачу)
После того, как отправили самые тяжелые грузы (которые больше средней загрузки вагона), пересчитываем среднее арифметическое, и начинаем укладывать грузы в вагоны, начиная с самого тяжелого. Возможны три стратегии.
1) Очередной (самый тяжелый из оставшихся) груз кладём в самый пустой вагон
2) Очередной груз кладём в самый загруженный из вагонов, в которые этот груз ещё помещается (т.е. общий вес вагона и груза не превосходит среднего арифметического)
3) Очередной груз кладём в случайный из вагонов, в которые груз помещается.
В стратегиях (2,3) иногда будет возникать ситуация "груз положить некуда". Тогда кладём его в самый пустой вагон, и отправляем.
Дальше надо экспериментировать, чтобы выбрать более подходящую из этих стратегий. Интуиция тут не очень помогает.

Если у вагона есть предел загрузки L, то груз, который не умещается даже в самый пустой вагон, оставляем до следующего поезда. При его загрузке сначала раскидываем очень тяжелые грузы, потом - оставленные от предыдущего поезда, потом - все новые.

Здесь достаточно перебора с помощью рекурсии.
Вам нужно заполнить прямоугольник M*N плитками размером 1*2.
Берёте массив A[M,N], заполняете его нулями.
Вызываете функцию Fill(A,1).
Fill(A,k){
Ищете первый элемент A[p,q], равный нулю.
Если не нашли - массив заполнен, печатаете его. return.
Если элемент A[p+1,q] существует и равен нулю, то в прямоугольник можно положить горизонтальную плитку: в A[p,q] и A[p+1,q] кладёте число k, вызываете Fill(A,k+1). Обнуляете A[p,q] и A[p+1,q].
Если элемент A[p,q+1] существует и равен нулю, то в прямоугольник можно положить вертикальную плитку: в A[p,q] и A[p,q+1] кладёте число k, вызываете Fill(A,k+1). Обнуляете A[p,q] и A[p,q+1].
}
Если бы надо было считать число способов заполнения, надо было бы смотреть в сторону динамического программирования.

Если это C++, то подойдёт такая формула:
M[i][j]=(abs(j-i)+1)*((i+j-N+1)*(i-j)>=0)
Если формулу хочется чисто математическую, то вместо ((i+j-N+1)*(i-j)>=0) можно написать (sign(2*(i+j-N+1)*(i-j)+1)+1)/2

Можно решить и за линейное время (после сортировок):
1) берём массив концов отрезков (xi,1) и (yi,-1), сортируем (не забывая, что при одинаковых первых числах сначала идут все начала отрезков, а потом все концы: так для отрезков [1,2] и [2,3] получим массив (1,1),(2,1),(2,-1),(3,-1))
2) берём массив длиной n (число точек), заполняем его числами от 1 до n (если пишем на C-подобных языках - то от 0 до n-1). Cортируем массив, используя условие less(a,b)=(P[a] < P[b]), где P - массив точек. Получим индексы точек, отсортированные по возрастанию координат соответствующих точек.
3) Идём по обоим массивам, сравниваем координаты. Когда проходим точку в массиве концов, то прибавляем к счётчику второй элемент. Когда достигаем координаты очередной точки из P - записываем в массив результатов значение счётчика. Не забываем, что точка P[a]=x обрабатывается после всех точек (x,1) но до всех точек (x,-1) из массива концов.
4) Выводим массив результатов.

Такие матрицы, судя по всему, описывают возможные бинарные операции на множестве {'a','b','c'}, т.е. функции от двух переменных из этого множества, принимающие значения в этом же множестве.
Всего таких функций будет 3^9=19683. Поэтому достаточно перебрать числа от 0 до 3^9-1, и троичную запись каждого из них превратить в матрицу. На C# это бы выглядело так:

char[,] matr=new char[3,3];
    for(int i=0;i<19683;i++){
        int a=i;
        for(int j=9;--j>=0;){
            matr[j/3,j%3]=(char)('a'+a%3);
            a/=3;
        }
        Process(matr);
    }

Уравнение x*ln(x)=c решать проще. Можно методом Ньютона. А можно и итерациями: x_{n+1}=c/ln(x_n), сходиться должно очень быстро.
UPD. Хотя нет, оно будет сходиться только при c>e. Метод Ньютона, всё-таки, надёжнее:
x_{n+1}=(c+x_n)/(ln(x_n)+1)

Здесь "изящное" и "быстроработающее" - слегка противоречивые требования. Быстрее всего будет определить число знаков делением пополам за 3-4 сравнения:

double mantissa(int c){
  int a=abs(c);
  int b=1;
  if(a>=100000){
    if(a>=10000000){
      if(a>=1000000000) b=1000000000;
      else if(a>=100000000) b=100000000;
      else a=10000000;
    }else if(a>=1000000) b=1000000;
    else b=100000;
  }else{
    if(a>=100){
      if(a>=10000) b=10000;
      else if(a>=1000) b=1000;
      else a=100;
    }else if(a>=10) b=10;
  }
  return (double)c/b;
}

но такой код трудно назвать красивым.
Лучше всего был бы цикл, но не с делением, а с целочисленным умножением на 10. Но там надо следить за переполнением.

Можно, конечно, и через float. Но там после вычисления порядка надо будет возвести 10 в нужную степень, а функция pow может оказаться для этого слишком долгой.

double mantissa(int a){
	if(a==0) return 0;
	float f=a;
	int b=((*(int*)&f&0x7fffffff)-0x40cd3ed7)/0x019a7daf;
	double d=a*pow(0.1,b);
	if(fabs(d)>=10) d/=10;
	return d;
}

Формула, несомненно, существует. Правда, в ней будут присутствовать корни многочлена (z^5-6*z^4+10*z^3-z^2-6*z+1)*(z^5-4*z^4+2*z^3+5*z^2-2*z-1) (неразрешимого в радикалах), и выписать её совсем не просто. Но, при большой необходимости, возможно.
Впрочем, если в формуле может присутствовать матрица, то ответ такой:

(1 1 1 1 1 1 1 1 1 1)*(M^(n-1))*transpose(0 1 1 1 1 1 1 1 1 1),

где M - матрица 10х10, в которой в клетках (m,n), для которых abs(m-n)<2, стоят единицы, а в остальных клетках - нули.

Насколько я понимаю, подобные массивы описываются здесь: habrahabr.ru/post/187882 Правда, там рассматривается частный случай - когда для каждой пары столбцов требуются все комбинации, а не только присутствующие в другом массиве. Но это не делает задачу легче.
А ортогональность (в смысле линейной алгебры) тут вообще ни при чём.