Списковый алгоритм решения задачи о сумме подмножества

@brrr · Регистрация: 26.10.2014

Студворк — интернет-сервис помощи студентам

Сделала две программы на matlab, вычисляющие сумму подмножества. На входе - множество и желаемая сумма, на выходе - сумма подмножества, наиболее близкая к заданной.
Первая программа вычисляет ближайшую слева сумму любого подмножества, вторая - вычисляет ближайшую слева сумму, корректна для 4х и менее элементов суммы, зато выдает суммируемые элементы подмножества.
Прошу оценить, указать на недоработки
Первая:

Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
%%списковый метод 
clc
clear
SpisokN=input('Введите массив: ')
s=input('Введите s: ')
n=length(SpisokN)
 
SpisokS(1)=SpisokN(1)
 
for i=2:n
    r=length(SpisokS)
    SpisokS(r+1)=SpisokN(i)
    h=r+1
    h=length(SpisokS)
    for j=1:r 
        m=length(SpisokS)
        SpisokS(m+1)=SpisokS(h)+SpisokS(j)
    end
end
 
SpisokSunique=unique(SpisokS)
n=length(SpisokSunique)
 
for i=1:n
    if SpisokSunique(i)<=s
        SpisokSlast(i) = SpisokSunique(i)
    end
end
 
k=length(SpisokSlast)
s1=SpisokSlast(k)

Вторая:

Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
%%списковый метод 
clc
clear
SpisokN=input('Введите массив: ')
s=input('Введите s: ')
% SpisokN=[10 15 30 15]
% s=30
n=length(SpisokN)
for i=1:n
massN(i,1)=SpisokN(i)
massN(i,2)=i
end
 
SpisokS(1)=SpisokN(1)
massS(1,1)=massN(1,1)
massS(1,2)=massN(1,2)
 
for i=2:n
    r=length(SpisokS)
    SpisokS(r+1)=SpisokN(i)
    massS(r+1,1)=massN(i,1)
    massS(r+1,2)=massN(i,2)    
    h=r+1
    h=length(SpisokS)
    for j=1:r 
        m=length(SpisokS)
        SpisokS(m+1)=SpisokS(h)+SpisokS(j)
        massS(m+1,1)=SpisokS(h)+SpisokS(j)
        massS(m+1,2)=0
        massS(m+1,3)=j
        massS(m+1,4)=h
    end
end
 
SpisokSunique=unique(SpisokS)
n=length(SpisokSunique)
 
for i=1:n
    if SpisokSunique(i)<=s
        SpisokSlast(i) = SpisokSunique(i)
    end
end
 
k=length(SpisokSlast)
s1=SpisokSlast(k)
 
for i=1:m+1 
   if massS(i,1)==s1
       mass1(i,1)=massS(i,1)
       mass1(i,2)=massS(i,2)
       mass1(i,3)=massS(i,3)
       mass1(i,4)=massS(i,4)
   end
end
 
mass2s=0
m=size(mass1,1)
for i=1:m
if mass1(i,1)~=0
    mass2(mass2s+1,1)=mass1(i,1)
    mass2(mass2s+1,2)=mass1(i,2)
    mass2(mass2s+1,3)=mass1(i,3)
    mass2(mass2s+1,4)=mass1(i,4)
     mass2s=size(mass2,1)
end
end
 
 
for i=1:mass2s 
    disp('Вариант подмножества:') 
    if mass2(i,2)~=0%
        s1=SpisokN(mass2(i,2))%
    else
        if massS(mass2(i,3),2)~=0%
           s2=SpisokN(massS(mass2(i,3),2))%
        else
            if massS(massS(mass2(i,3),3),2)~=0%
                s3=SpisokN(massS(massS(mass2(i,3),3),2))%
            else 
                s4=SpisokN(massS(massS(massS(mass2(i,3),3),3),2))%
                s4=SpisokN(massS(massS(massS(mass2(i,3),3),4),2))%
            end
            if massS(massS(mass2(i,3),4),2)~=0%
                s3=SpisokN(massS(massS(mass2(i,3),4),2))%
            else 
                s4=SpisokN(massS(massS(massS(mass2(i,3),4),3),2))%
                s4=SpisokN(massS(massS(massS(mass2(i,3),4),4),2))%
            end
        end
        if massS(mass2(i,4),2)~=0%
           s2=SpisokN(massS(mass2(i,4),2))%
        else
            if massS(massS(mass2(i,4),3),2)~=0%
                s3=SpisokN(massS(massS(mass2(i,4),3),2))%
            else 
                s4=SpisokN(massS(massS(massS(mass2(i,4),3),3),2))%
                s4=SpisokN(massS(massS(massS(mass2(i,4),3),4),2))%
            end
            if massS(massS(mass2(i,4),4),2)~=0%
                s3=SpisokN(massS(massS(mass2(i,4),4),2))%
            else 
                s4=SpisokN(massS(massS(massS(mass2(i,4),4),3),2))%
                s4=SpisokN(massS(massS(massS(mass2(i,4),4),4),2))%
            end
        end
    end
   
end

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом