c программирование головоломки

Question

Учитывая массив, все элементы которого являются положительными числами, найдите максимальную сумму подпоследовательности с ограничением, что никакие 2 числа в последовательности не должны быть смежными в массиве. Таким образом, 3 2 7 10 должно возвращать 13 (сумма 3 и 10) или 3 2 5 10 7 должно возвращать 15 (сумма 3, 5 и 7).

Я попробовал использовать все возможные разрешенные суммы, а затем найти максимум (метод грубой силы), но есть ли лучший метод. Например, для [3 2 7 10] я суммирую 3,7 и 2,10 и беру максимум.

---

Больше примеров:

• [ 3 , 2, 7 , 1]: возврат 10
• [ 6 , 2, 1, 4 ]: возврат 10
• [ 8 , 9, 5 , 1]: возврат 13
• [29, 77 , 16]: возврат 77
• [ 29 , 44, 16 ]: возврат 45

Answer 1

Эту проблему можно решить с помощью динамического программирования.

Допустим, у нас есть массив целых чисел:

i[1], i[2], i[3], ..., i[n], i[n+1], i[n+2]

Мы разбиваем массив на две части: первая часть содержит первые n целых чисел, а вторая часть - последние два целых числа:

{i[1], i[2], i[3], ..., i[n]}, {i[n+1], i[n+2]}

Обозначим M_SUM(n) как максимальную сумму первых n целых чисел по вашему требованию.

Будет два случая:

1. если i[n] не учитывается в M_SUM(n), то M_SUM(n+2) = M_SUM(n) + MAX(i[n+1], i[n+2])
2. если i[n] засчитано в M_SUM(n), то M_SUM(n+2) = M_SUM(n) + i[n+2]

тогда M_SUM(n+2), значение, которое мы ищем, будет большим значением из вышеупомянутых двух.

Тогда у нас может быть очень наивный псевдокод, как показано ниже:

function M_SUM(n)
   return MAX(M_SUM(n, true), M_SUM(n, false))

function M_SUM(n, flag)
   if n == 0 then return 0
   else if n == 1
      return flag ? i[0] : 0
   } else {
      if flag then
         return MAX(
                M_SUM(n-2, true) + i[n-1], 
                M_SUM(n-2, false) + MAX(i[n-1],i[n-2]))
      else
         return MAX(M_SUM(n-2, false) + i[n-2], M_SUM(n-2, true))
   }

«флаг» означает «разрешить использование последнего целого числа»

Этот алгоритм имеет экспоненциальную сложность по времени.

Методы динамического программирования могут использоваться для устранения ненужного пересчета M_SUM.

Сохранение каждого M_SUM(n, flag) в матрицу n * 2. В части рекурсии, если такого значения нет в матрице, вычислите его. В противном случае просто получите значение из матрицы. Это уменьшит сложность времени до линейной.

Алгоритм будет иметь O (n) временную сложность и O (n) пространственную сложность.

Answer 2

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)

Answer 3

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

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

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

альтернативный текст http://img44.imageshack.us/img44/4843/newgp.jpg

Ответом будет не более двух значений в последнем столбце (выделено красным)

Answer 4

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();
        }
    }
}

Answer 5

пакет com.dan.alg.recursion;

/ ** * Вопрос: Учитывая массив положительных чисел, найдите максимальную сумму подпоследовательности * с условием, что никакие 2 числа в последовательности не должны быть смежными в массиве. * Таким образом, 3 2 7 10 должно вернуть 13 (сумма 3 и 10) или 3 2 5 10 7 должно вернуть 15 * (сумма 3, 5 и 7). Ответьте на вопрос наиболее эффективным способом. *

* Решение: мы будем рекурсивно строить решение в обратном направлении (начиная с последней позиции * массива и проработав путь к его началу), основываясь на следующем наблюдении: *

* Максимальная сумма для позиции p может быть получена из максимума следующих двух значений: * V1 = значение для позиции p + максимальная сумма для позиции p - 2 (помните, два элемента не могут быть смежными) * V2 = максимальная сумма для позиции p - 1 * * @author dan * /

публичный класс MaxSumNoNeighbours {

private static int [] arr = { 29, 44, 16 };

/**
 * Determine the max sum for the current position.
 * 
 * @param currentPos    the current position in the array.
 */
private static int maxSum(final int currentPos) {
    //  The sum is zero if we are outside of the bounds.
    if (currentPos < 0) {
        return 0;
    }

    return Math.max(
            arr[currentPos] + maxSum(currentPos - 2), 
            maxSum(currentPos - 1));
}

public static void main (final String [] args) {
    //  Start from the end of the array and work your way forwards
    System.out.println(maxSum(arr.length - 1));
}

}

Answer 6

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));
}

max - это функция, позволяющая получить максимум из двух.

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

Answer 7

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

Answer 8

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;
    }
}

Answer 9

{

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);
}

Answer 10

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

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