Сделала две программы на matlab, вычисляющие сумму подмножества. На входе - множество и желаемая сумма, на выходе - сумма подмножества, наиболее близкая к заданной.
Первая программа вычисляет ближайшую слева сумму любого подмножества, вторая - вычисляет ближайшую слева сумму, корректна для 4х и менее элементов суммы, зато выдает суммируемые элементы подмножества.
Прошу оценить, указать на недоработки
Первая:
Код :
  1. %%списковый метод
  2. clc
  3. clear
  4. SpisokN=input('Введите массив: ')
  5. s=input('Введите s: ')
  6. n=length(SpisokN)
  7.  
  8. SpisokS(1)=SpisokN(1)
  9.  
  10. for i=2:n
  11.     r=length(SpisokS)
  12.     SpisokS(r+1)=SpisokN(i)
  13.     h=r+1
  14.     h=length(SpisokS)
  15.     for j=1:r
  16.         m=length(SpisokS)
  17.         SpisokS(m+1)=SpisokS(h)+SpisokS(j)
  18.     end
  19. end
  20.  
  21. SpisokSunique=unique(SpisokS)
  22. n=length(SpisokSunique)
  23.  
  24. for i=1:n
  25.     if SpisokSunique(i)<=s
  26.         SpisokSlast(i) = SpisokSunique(i)
  27.     end
  28. end
  29.  
  30. k=length(SpisokSlast)
  31. s1=SpisokSlast(k)

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