c программирующий загадку

F # Решение:

let rec maxsubset = function
    | [] -> 0
    | x::[] -> x
    | x::y::xs -> max (maxsubset (y::xs)) (x + maxsubset xs)

Легко адаптируется к C-подобным языкам:

using System;
using System.Linq;

namespace Juliet
{
    class Program
    {
        static int MaxSubset(int[] arr, int offset)
        {
            if (offset >= arr.Length)
                return 0;
            else
                return Math.Max(MaxSubset(arr, offset + 1), arr[offset] + MaxSubset(arr, offset + 2));
        }

        static void Test(params int[] nums)
        {
            Console.WriteLine("----------------");
            Console.WriteLine("MaxSubset({0}) = {1}", String.Join(", ", nums), MaxSubset(nums, 0));
        }

        static void Main(string[] args)
        {
            Test(3, 2, 7, 1);
            Test(6, 2, 1, 4);
            Test(8, 9, 5, 1);
            Test(29, 77, 16);
            Test(29, 44, 16);
            Test(239, 2, 3, 111, 1, 4, 546, 4, 3);
            Test(100, 1, 1, 100);
            Console.ReadLine();
        }
    }
}

sum[0] = 0;
sum[1] = 0;

for(i = 0; i < arraylength; i++) 
    sum[i & 1] += array[i];

printf("sum = %u\n", MAX(sum[0], sum[1]));
printf("homework completed\n");

Симпатичная проблема. Самый простым подходом, кажется, следует учитывать итеративно, поддерживая две лучшие суммы: лучшая сумма, которую вы можете получить при использовании [I], допускается, и лучшая сумма, которую вы можете получить при использовании [i] MinueN т быть допускается. В Python:

def best(arr):
    # best sums of zero length array are 0
    ok, bad = 0,0 

    for x in arr:
        # best sum if we can use x is to use it,
        # because all elements are positive
        ok += x

        # moving along one step means we can't
        # use the ok sum, and can use the bad sum
        bad, ok = ok, bad

        # but just because we could use ok, doesn't
        # mean we have to, so if it's better, use
        # that path
        if bad < ok:
            bad = ok

    # bad is then our best possible sum
    return bad

int findSum(int* arr, int sz)
{
    if( sz <= 0) return 0;

    if( sz == 1)
    {
        return arr[0];
    }
    else
    {
        int a = arr[0] + findSum(arr+2, sz-2); 

        int b = findSum(arr+1, sz-1);

        if( a >= b)
            return a;
        else 
            return b;
    }
}

Позвольте мне попробовать еще раз....

CREATE FUNCTION saneDecimal(@input decimal(5,2)) returns varchar(10)
AS
BEGIN
DECLARE @output varchar(10)
SET @output = CAST(@input AS varchar(10))

DECLARE @trimmable table (trimval char(1))
INSERT @trimmable VALUES ('0')
INSERT @trimmable VALUES ('.')

WHILE EXISTS (SELECT * FROM @trimmable WHERE trimval = CAST(SUBSTRING(@output, LEN(@output), 1) AS char(1)))
    SET @output = LEFT(@output, LEN(@output) - 1)

RETURN @output
END

GO

SELECT dbo.saneDecimal(1.00)

Возможно, более подходящим является рингбуфер. Это не список, хотя вполне вероятно, что он может вести себя достаточно, как список для ваших целей.

Проблема заключается в том, что эффективность сдвига в списке равна O (n), что становится значительным для достаточно больших списков.

Переключение в рингбуфере - это просто обновление местоположения головки, которое равно O (1)

Рассмотрим средний элемент, он может быть частью решения или нет. Для каждого случая найдите лучшие решения для левого и правого оставшихся подперечислять и объедините их, затем выберите лучшее из двух случаев.

Python, шесть строк, использующих динамическое программирование ( не совсем! См. Редаж ниже. ):

def run(x):
    if len(x) == 0:
        return 0
    elif len(x) <= 2:
        return max(x)
    return max(x[0] + run(x[2:]), x[1] + run(x[3:]))

Редактирование и откат: Хотя решение выше генерирует правильный ответ, это не ] Динамическое программирование. Ниже приведен ниже, и он использует меньше функциональных вызовов:

def main(x):
    return max(helper(x))

def helper(x):
    if len(x) == 1:
        return (0, x[0])
    a, b = helper(x[:-1])
    return (max(a, b), x[-1] + a)

{

int a[10]={1,2,3,4,5,6,7,89,8,9};

int k=0,i,j,l;
int sum[36],max;

for (i=0;i<10;i++)
{
for (j=i+2;j<10;j++,k++)
sum[k]=a[i]+a[j];
}
max=a[0];
for(i=0;i<36;i++)
printf("sum[%d] is %d\n",i,sum[i]);

for(l=1;l<36;l++)
{
if(max>sum[l])
continue;
else
max=sum[l];
}
printf("%d is the max sum",max);
}

int choose( int n)
{
   if((n==1) || (n==0))
       return array[n];
   if( n==2)
       return array[0];

   totalSum += max(choose(n-2), choose(n-3));
}

Макс - это функция, чтобы получить максимум отсутствие из двух.

Для массива «массив», сделайте вызов функции для каждого элемента массива и хранить максимальный результат в другом массиве (скажем, arrayofmax [n])

Возьмем, например, [3,2,5,10,7]

Решение с использованием динамического программирования:

Содержите два массива, как показано в последних двух строках

alt текст http://img44.imageshack.us/img44/4843/newgp.jpg

Ответ будет максимум два значения в последнем столбце (красным жирным шрифтом)