Сумма

[RIP VIP]

Дан массив N натуральных чисел. Требуется найти все возможные суммы элементов массива, причем в сумму не может входить элемент массива с одним и тем же значением более одного раза. Сумму из одного слагаемого не учитывать.

Пример: 2, 2, 4, 1, 1, 1
Ответ: 3, 5, 6, 7

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

[eoln]

Пример: 2, 2, 4, 1, 1, 1
Ответ: 3, 5, 6, 7

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

Гм... сумма любых двух элементов... а как 7 получилось... из двух то элементов

Const
  Mas: Array[1..6] of Integer = (2, 2, 4, 1, 1, 1);
Var 
  NewMas: Array[1..6] of Integer;
  Count: Integer;
...
Begin
  //Сначала уберём все повторяющиеся числа
  For I := 1 to 6 do begin
    b := true;
    For J := 1 to 6 do
    If (Mas[I] = Mas [J]) and (I<>J) then b := false;
    If b then Inc(Count);
    NewMas[Count] := Mas[I]
  end;
  ...
  //А затем циклом все суммы перебираем и сортируем в новый массив SumMass например
  //и если в сортированнои массиве SumMas[I] <> SumMas[I+1] тогда выписываем его значение
  //По-моему это оптимальный способ
End.

[дмидми]

Значений в наличии - три: 1, 2, 4.
Сочетаний из трёх - семь: 1, 2, 4, 1+2=3, 1+4=5, 2+4=6, 1+2+4=7
В ответе - четыре последних варианта.

Что, сумма из одного слагаемого - не сумма? Ну, это где угодно, только не в программировании Однако - плетью обуха...

Массив значений, пожалуй, я бы заполнял так:

count:=0
for i:=1 to 6 begin
	b:=true;
	for j:=1 to count
		if Mas[i]=NewMas[j] then b:=false;
	if b then begin
		count:=count+1;
		NewMas[count]:=Mas[i]
	end
end;

(Sorry, Паскаля у меня нет, и не писал я на нём лет... Лучше не вспоминать, сколько. Что-нибудь вроде Exit For в нём есть?)

Осталось соорудить сочетания из count по "от двух до count", без перестановок, и просуммировать (скорее всего, попутно).

Рекурсии разрешены?

P.S. Сортировать NewMas, конечно, незачем.

[RIP VIP]

Сообщение от eoln

Гм... сумма любых двух элементов... а как 7 получилось... из двух то элементов

У меня-то как раз и не получилось =) Там ведь пример написан

Что, сумма из одного слагаемого - не сумма?

В рамках данной задачи нет.

Массив значений, пожалуй, я бы заполнял так...

Спасибо, конечно, но с заполнением массива значений у меня проблем не возникло.

Сообщение от eoln

А затем циклом все суммы перебираем

А вот с перебором всех сумм как раз проблемы... Можно поподробней?

Sorry, Паскаля у меня нет

Можно и на си...

Рекурсии разрешены?

Да

Осталось соорудить сочетания из count по "от двух до count", без перестановок, и просуммировать (скорее всего, попутно)

Не совсем понял((

[evg_m]

рекурсия ( текущая сумма, индекс последнего использованного)

для каждого индекса из оставшихся

добавить индекс к текущей сумме и внести в список

рекурсия ( сумма, индекс)

[RIP VIP]

Что-то в этом есть... сейчас буду пробовать...

[дмидми]

Пример самого тупого перебора с жёстким ограничением по числу элементов исходного множества.

Си под рукой тоже нет %)
Слепил на VBA. Можно создать новую книгу Excel, добавить в нее модуль и вставить в него

Option Explicit
Option Base 1

Sub RIP_VIP()
    Const P As Long = 2
    Dim i As Long, j As Long, Cnt As Long
    Dim msk As Long, c As Long, nm, s
    
    nm = Array(1, 2, 4) '1 to Cnt
    Cnt = UBound(nm)
    
    'Выбираем все непустые подмножества множества nm
    For msk = 1 To 2 ^ Cnt - 1
        s = 0: c = 0
        For i = 1 To Cnt
            If 2 ^ (i - 1) And msk Then s = s + nm(i): c = c + 1
        Next
        'Учитываем только подмножества,
        'состоящие не менее чем из P элементов
        If c >= P Then WriteOut (s)
    Next
End Sub

Private Sub WriteOut(s)
    ActiveCell = s
    ActiveCell.Offset(1).Select
End Sub

[RIP VIP]

Что-то показывает похожее на ответ...

[дмидми]

Ай-яй-яй... Это я что-то упустил Пр-роклятый склероз...
Почти офтоп: а пустое множество у вас, поди, и вовсе за множество не держат?