Program który pokaże jakie liczby dodac aby otrzymać wynik

[krystiandj]

Tak jak w temacie, chodzi o to że mam liczby np:

20
40
10
70
30

Chce z tych liczb otrzymać wynik np. 90 i teraz program wypisze mi że potrzebuje liczb 70+20 aby otrzymać ten wynik. Nie mam pojęcia jak to zrobić, czy jest ktoś w stanie coś pomóc ?

[IZZER4]

Bardzo proste

#include <string.au3>

global  $liczby[5] = ['20','40','10','70','30']
For $x = 0 To UBound($liczby) - 1
   For $y = 0 To UBound($liczby) -1
	  If $liczby[$x] + $liczby[$y] = 90 Then
		 MsgBox(0,'','Liczby to ' & $liczby[$x] & ',' & $liczby[$y])
		 EndIf
	  Next
   Next

[krystiandj]

Ale chodzi mi o to że mam tych liczb np 50 i teraz chce z nich wynik 1000 a ten program dodaje tylko dwie liczby, i właśnie nie mam pomysłu jak to zrobić

 

edit

Zrobiłem to w ten sposób na że dodaje 3 razy ale to bym musiałbym cały czas dopisywać zmienne, i jeszcze jest jeden problem bo jak mam np 10+20+30 i teraz dam że chce wynik 20 to on mi doda 10+10 czyli dwa razy użyje zmienną

For $x = 0 To UBound($liczby) - 1
	   For $y = 0 To UBound($liczby) -1
		  If $liczby[$x] + $liczby[$y] = $suma Then
			 MsgBox(0,'','Liczby to ' & $liczby[$x] & ',' & $liczby[$y])
		  Else
			  For $z = 0 To UBound($liczby) -1
				If $liczby[$x] + $liczby[$y] + $liczby[$z] = $suma Then
					MsgBox(0,'','Liczby to ' & $liczby[$x] & ',' & $liczby[$y] & ',' & $liczby[$z])
				EndIf
			  Next
		   EndIf
	   Next
	Next

[IZZER4]

Chciales z dwoch otrzymac wynik to ci napisalem

Innego rozwiazania tutaj nie widze.

[Sopelek997]

Sprawdzaj rekurencyjne wszystkie możliwości (przy każdym wywołaniu przechowuj jakie były poprzednie liczby), wychodź z rekurencji jeśli suma >=  1000. Jeśli suma będzie równa to dodatkowo dodaj te kolejne liczby do listy poprawnych odpowiedzi.

 

Pozostaje problem wykluczenia identycznych odpowiedzi. Można to zrobić poprzez zrobienie tego tak, że z każdym rozgałęzieniem dodajesz tylko te liczby, które są później niż poprzednia (ewentualnie też ta co poprzednia jeśli chcesz mieć możliwe dodawanie tych samych kilka razy)

[krystiandj]

"Sprawdzaj rekurencyjne wszystkie możliwości... "

 

Właśnie to jest problemem jak to zrobic ?

[Sopelek997]

Rozgałęziasz rekurencję przy każdej wartości w tablicy (która jest po aktualnej). Za każdym razem sumując.

[krystiandj]

czyli musiał bym zrobić tyle pętli ile jest miejsc w tablicy a to były bo bez sensu bo za każdym razem będę potrzebował inną ilość 

[Sopelek997]

No właśnie nie. Od tego masz rekurencję.

[krystiandj]

Nie ogarniam, próbuje i wychodzą mi programy które do niczego nie prowadzą 

[_LostGalaxy_]

A w google chociaż szukałeś?

 

http://en.wikipedia.org/wiki/Subset_sum_problem

http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/

http://www.cs.utsa.edu/~wagner/CS3343/ss/ss.html

[Ballas]

#include <Array.au3>

 

Global $liczba[10]

$liczby = ""

$liczba[0] = 50

$liczba[1] = 20

$liczba[2] = 20

$liczba[3] = 40

$liczba[4] = 10

$liczba[5] = 60

$liczba[6] = 70

$liczba[7] = 100

$liczba[8] = 90

$liczba[9] = 80

_ArraySort($liczba)

$doznalezienia = 450

$doznalezienia_ = $doznalezienia

 

For $i = UBound($liczba)-1 To 0 Step -1

If $liczba[$i] <= $doznalezienia Then

$liczby &= $liczba[$i]&","

$doznalezienia -= $liczba[$i]

EndIf

If $doznalezienia = 0 Then ExitLoop

Next

 

If $doznalezienia <> 0 Then

MsgBox(0,"","Z tych liczb nie można uzyskać wyniku: "&$doznalezienia_)

Else

MsgBox(0,"",$liczby)

EndIf

[_LostGalaxy_]

@Ballas

 

No chyba jednak nie...

Testowałeś to w ogóle?

 

Sprawdź co ten programik zwróci dla tablicy:

{ 30, 20, 20, 20, 80 }

, z suma 90.

 

No pokazuje, że się nie da uzyskać a ja widzę, że się da: 20+20+20+30=90.

[Ballas]

A gdzie w pierwszym poście mistrzu widzisz powtarzające się liczby 

[_LostGalaxy_]

A gdzie w pierwszym poście mistrzu widzisz powtarzające się liczby 

 

Lol... ale to nie w tym jest problem. Ty chyba nie wiesz jak działa to coś co napisałeś. No i tak BTW. to w pierwszym poście nigdzie nie ma załozenia, że nie mogą sie powtarzac, więc mogą.

 

Masz kolejny przykład:

Tablica:

{ 40, 50, 80 }

i suma 90.

 

Ojojojoj... nic sie nie powtarza a ten inteligentny program znowu pokazuje ze sie nie da. No chyba ze wedlug ciebie 40+50 nie jest rowne 90...

[krystiandj]

mogą się powtarzać te liczby z których mają powstawac liczby, ale nie tak że mam np 50,20,20,10 i chce wynik 60 a on mi zrobi 3 razy 20 czyli 20+20+20 bo tej jednej 20 nie ma

 

 

Program od Ballas wydaje się dobrze działać, mam jeszcze pytanie dlaczego jak zrobie 

	$liczba = StringSplit(GUICtrlRead($Edit1),"+")

czyli z edita odczytam liczby np. 10+20+30+40+50+60+70+80+90+100 i rozdzielam je + do tablicy wtedy program nie chce działać

[Sopelek997]

Program od Ballas wydaje się dobrze działać

 

Z jego przykładem tak...

 

mogą się powtarzać te liczby z których mają powstawac liczby, ale nie tak że mam np 50,20,20,10 i chce wynik 60 a on mi zrobi 3 razy 20 czyli 20+20+20 bo tej jednej 20 nie ma

 

Jak zrobisz tak jak ci mówimy to będziesz miał wszystkie możliwe.