Другой способ выполнения задания - использовать аналитическую функцию MAX () в предложении OVER PARTITION
SELECT t.*
FROM
(
SELECT id
,rev
,contents
,MAX(rev) OVER (PARTITION BY id) as max_rev
FROM YourTable
) t
WHERE t.rev = t.max_rev
. Другое решение OVER PARTITION, уже зарегистрированное в этом сообщении, -
SELECT t.*
FROM
(
SELECT id
,rev
,contents
,ROW_NUMBER() OVER (PARTITION BY id ORDER BY rev DESC) rank
FROM YourTable
) t
WHERE t.rank = 1
Этот 2 SELECT хорошо работает на Oracle 10g.
Этот частный случай проблемы Кнэпсака называется Subset Sum .
Существует дешевая надстройка Excel, которая решает эту проблему: SumMatch
[/g1]
Excel Solver Addin, опубликованный на сайте superuser.com, имеет отличное решение (если у вас есть Excel) https://superuser.com/questions/204925/excel-find-a-subset-of-numbers -Вот-дополнения к-а дарованное итог
C # версия
установочный тест:
using System;
using System.Collections.Generic;
public class Program
{
public static void Main(string[] args)
{
// subtotal list
List<double> totals = new List<double>(new double[] { 1, -1, 18, 23, 3.50, 8, 70, 99.50, 87, 22, 4, 4, 100.50, 120, 27, 101.50, 100.50 });
// get matches
List<double[]> results = Knapsack.MatchTotal(100.50, totals);
// print results
foreach (var result in results)
{
Console.WriteLine(string.Join(",", result));
}
Console.WriteLine("Done.");
Console.ReadKey();
}
}
код:
using System.Collections.Generic;
using System.Linq;
public class Knapsack
{
internal static List<double[]> MatchTotal(double theTotal, List<double> subTotals)
{
List<double[]> results = new List<double[]>();
while (subTotals.Contains(theTotal))
{
results.Add(new double[1] { theTotal });
subTotals.Remove(theTotal);
}
// if no subtotals were passed
// or all matched the Total
// return
if (subTotals.Count == 0)
return results;
subTotals.Sort();
double mostNegativeNumber = subTotals[0];
if (mostNegativeNumber > 0)
mostNegativeNumber = 0;
// if there aren't any negative values
// we can remove any values bigger than the total
if (mostNegativeNumber == 0)
subTotals.RemoveAll(d => d > theTotal);
// if there aren't any negative values
// and sum is less than the total no need to look further
if (mostNegativeNumber == 0 && subTotals.Sum() < theTotal)
return results;
// get the combinations for the remaining subTotals
// skip 1 since we already removed subTotals that match
for (int choose = 2; choose <= subTotals.Count; choose++)
{
// get combinations for each length
IEnumerable<IEnumerable<double>> combos = Combination.Combinations(subTotals.AsEnumerable(), choose);
// add combinations where the sum mathces the total to the result list
results.AddRange(from combo in combos
where combo.Sum() == theTotal
select combo.ToArray());
}
return results;
}
}
public static class Combination
{
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int choose)
{
return choose == 0 ? // if choose = 0
new[] { new T[0] } : // return empty Type array
elements.SelectMany((element, i) => // else recursively iterate over array to create combinations
elements.Skip(i + 1).Combinations(choose - 1).Select(combo => (new[] { element }).Concat(combo)));
}
}
результаты:
100.5
100.5
-1,101.5
1,99.5
3.5,27,70
3.5,4,23,70
3.5,4,23,70
-1,1,3.5,27,70
1,3.5,4,22,70
1,3.5,4,22,70
1,3.5,8,18,70
-1,1,3.5,4,23,70
-1,1,3.5,4,23,70
1,3.5,4,4,18,70
-1,3.5,8,18,22,23,27
-1,3.5,4,4,18,22,23,27
Done.
Если subTotals повторяются, появляются дублирующие результаты (желаемый эффект). В действительности вы, вероятно, захотите использовать subTotal Tupled с некоторым ID, чтобы вы могли связать его с вашими данными.
В зависимости от ваших данных вы можете сначала просмотреть процентную ставку каждой транзакции. Как и в вашем первом примере, вы знаете, что 2.50 должно быть частью общей суммы, потому что это единственный набор транзакций с ненулевым процентом, которые добавляют к 50.
Не суперэффективное решение, но реализация реализаций в файле coffeescript
combinations
возвращает все возможные комбинации элементов в list
combinations = (list) ->
permuations = Math.pow(2, list.length) - 1
out = []
combinations = []
while permuations
out = []
for i in [0..list.length]
y = ( 1 << i )
if( y & permuations and (y isnt permuations))
out.push(list[i])
if out.length <= list.length and out.length > 0
combinations.push(out)
permuations--
return combinations
, а затем find_components
использует его, чтобы определить, какие числа добавляются до total
find_components = (total, list) ->
# given a list that is assumed to have only unique elements
list_combinations = combinations(list)
for combination in list_combinations
sum = 0
for number in combination
sum += number
if sum is total
return combination
return []
. Вот пример
list = [7.2, 3.3, 4.5, 6.0, 2, 4.1]
total = 7.2 + 2 + 4.1
console.log(find_components(total, list))
, который возвращает [ 7.2, 2, 4.1 ]
Если я правильно понимаю вашу проблему, у вас есть набор транзакций, и вы просто хотите знать, какие из них могли быть включены в данную сумму. Поэтому, если есть 4 возможных транзакции, тогда есть 2 ^ 4 = 16 возможных наборов для проверки. Эта проблема заключается в том, что для 100 возможных транзакций пространство поиска имеет 2 ^ 100 = 1267650600228229401496703205376 возможных комбинаций для поиска. Для 1000 потенциальных сделок в соединении, он растет в общей сложности
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
наборов, которые вы должны проверить. Жесткая сила вряд ли станет жизнеспособным решением этих проблем.
Вместо этого используйте решатель, способный справиться с проблемами knackack . Но даже тогда я не уверен, что вы можете создать полное перечисление всех возможных решений без какого-либо изменения грубой силы.
Его вроде как 0-1 проблема Knapsack, которая NP-полная и может быть решена посредством динамического программирования в полиномиальное время.
http://en.wikipedia.org/wiki/Knapsack_problem
Но в конце алгоритма вам также необходимо проверить, что сумма что вы хотели.