Экспресс целого числа в виде суммы некоторых других фиксированных целых

у меня есть фиксированный список весов:Экспресс целого числа в виде суммы некоторых других фиксированных целых

int[] weights = new int[] { 10, 15, 20 };

и цель:

int target = 28;

Я ищу алгоритм, чтобы выразить target, как сумма элементов из weights (с допускаемыми повторами), так что target либо согласован, либо превышен, достигается максимально возможное совпадение с target, и в этом случае Номер используемых весов минимизирован.

Так что с выше входом я хотел либо 10 20 или 15 15 быть возвращены, так как 30 так близко, как мы можем получить, и вариантов решений 30, эти два лучше, чем 10 10 10.

С target из 39, выход должен быть 20 20, а не, скажем, 15 15 10 или 10 10 10 10.

С target от 14 выход должен быть 15.

Есть ли хороший подход здесь, кроме обычных петлей foreach? Я думал о том, чтобы получить наибольшее значение, доступное в массиве, и проверить, является ли цель отрицательной, если нет, то давайте перейдем к следующему значению.

Это не домашняя :)

источник

2012-07-10 Eric Herlitz

Я не понимаю _ «Если бы мой вес был бы равен 39, результат был бы равен 20 и 20.» _ В массиве всего 20. –

Итак, вы можете выбрать одно и то же значение несколько раз из массива и хотите, чтобы сумма выбранных значений была больше или равна целевому значению. Предположительно, вы хотите получить минимально возможную сумму и * также *, чтобы свести к минимуму количество выбранных значений? Например. 10, 10, 10 является худшим выбором, когда цель = 28? –

Я не понимаю '' В приведенном выше примере выбор должен быть 20 и 10 ". Почему 10? –

Мне удалось найти решение, благодаря каждому здесь, что делает его более понятным, что мне действительно нужно. Это не самый красивый код, который я написал, но это MVP-разработка в любом случае!

private static List<int> WeightsJuggle(List<int> packages, IOrderedEnumerable<int> weights, int weight) 
{ 
    if (weight == 0) 
     return packages; 

    foreach (int i in weights.Where(i => i >= weight)) 
    { 
     packages.Add(i); 
     return packages; 
    } 

    packages.Add(weights.Max()); 
    return WeightsJuggle(packages, weights, weight - weights.Max()); 
}

Я называю это, как этот

IOrderedEnumerable<int> weights = new int[] { 10, 15, 20 }.OrderBy(x => x); 
int weight = 65; 
List<int> packages = new List<int>();

Тест с весом 65

enter image description here

Тест с весом 123

enter image description here

источник

2012-07-10 09:16:07

Не работает. Попробуйте его с помощью 'weight = 30'. Результатом будет '20, 15', но это должно быть либо' 20, 10', либо '15, 15'. – sloth

Правильно, исправлено это. –

Это известно как knapsack problem. Единственная разница в том, что вы ищете ближайший матч, а не ближайший нижний матч. К счастью, ни один из весов не имеет другого значения. Трудность заключается в том, что вы не можете просто использовать один из weights, который ближе всего подходит и рекурсивно, используя оставшееся значение (комбинация меньших значений иногда лучше подходит).

В вашем примере weights все имеют 5 "единиц" между ними, если это всегда так, проблема будет намного легче решить.

источник

2012-07-10 08:30:38

Экспресс целого числа в виде суммы некоторых других фиксированных целых

ответ

Смежные вопросы