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

Ответить

Код подтверждения
Введите код в точности так, как вы его видите. Регистр символов не имеет значения.
BBCode ВКЛЮЧЁН
[img] ВКЛЮЧЁН
[url] ВКЛЮЧЁН
Смайлики ОТКЛЮЧЕНЫ
Обзор темы
   

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

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

Maria_Z » 28 май 2015, 08:27

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

Код: Выделить всё

%%списковый метод 
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)
Вторая:

Код: Выделить всё

%%списковый метод 
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

Вернуться к началу