sayıları iki ayrı kümeye ayırmak

[Bone]

kolay bir olaya benziyor gerçi ama deneyince nasıl çözülceğini bulamadım.

elimizde random adet random sayılar var.
(örneğin random adetimiz 9,
random sayılar ise 1 3 5 7 8 10 14 16 20 olsun.)
bu sayıları iki kümeye ayırcağız,
sayılar kümelere öyle sıralancak ki,
her kümenin içindeki sayıların toplamı,
iki kümenin de birbirlerine en yakın toplama değerlerine sahip olmasını sağlıyacak.

biraz karışık bir anlatım oldu ama,
sadeleştirmek için sayıları 1-2-3-4 yapalım.
bu sayıları iki kümeye, 1-3 x 2-4, 1-2 x 3-4, 1 x 2-3-4, 1-3-4 x 2 gibi farklı şekillerde ayırabiliriz.
fakat iki kümeyi 1-4 ve 2-3 diye ayırdığımız durumda,
1 ve 4'ün toplamı 5, 2 ve 3'ün toplamı 5 oluyor,
ve iki küme birbirine olabilecek en yakın toplamları elde ediyor. ve cevabımız A: 1,4, B: 2,3 olmuş oluyor.

kümeler tam olarak birbirine eşit olmak zorunda da değiller.
bir başka örnek olarak, 1-2-3-4-5 yapalım.
1-2-5 ile 3-4'ü ayrı kümelere koyduğumuzda, bir kümenin toplamı 8, diğerininki 7 ediyor. iki kümenin birbirine en yakın olduğu değerler bunlar.
bu durumda cevabımız A: 1,2,5, B: 3-4 oluyor.

yani
1 3 5 7 8 10 14 16 20 sayılarını A ve B diye ayırdığımızda,
A ve B kümeleri, kombinasyonlar arasında, mümkün olan en yakın değerlere sahip olması gerekiyor.

herhangi bir sayı listesini bahsettiğim şekilde iki ayrı kümeye ayırmak için nasıl bir programlama yapmak gerek.
herhangi bir dil kullanabilirsiniz, C, Java, PHP vs...

[fizban]

NP bu problem. Tum cozumleri enumerate etmen lazim.

[Bone]

illa olasılıkları tek tek hesaplatçaz yani?

[Vidar]

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

[Havenless]

Bütün sayıları dizi olarak ataman gerek önce, sonra teker teker sıralı bir biçimde bunları her sayıyla ayrı ayrı toplatarak en baştaki büyük kümenin toplamının yarısından küçük olacak şekilde elde ettiğin toplamları toplamaya başlayacaksın rastgele. Algoritmayı çıkarttım gibi ama yazmak epey uzun olur.

Sayılar toplanırken elde ettiğin toplamları iki ayrı dizide toplayacaksın, yine bu döngü iki kümenin toplamı eşitleninceye kadar sürecek büyük olasılıkla.

[Bone]

eyvallah o zaman
sağol

[Havenless]

Formülü yeni gördüm bu arada, daha doğru sanırım o, toplamı maximize ettiğinden orada büyük eşit kullanmış.

[Sawer]

direk knapsack