Program İçin Algoritma Önerisi
-
Evet, kesinlikle süper olmuş ve mantık doğru. Ancak bir de c++ kodunu alabilirmiyim :D (Yüzsüz Mürid oldum bende)
-
HolyOne bunu yazdı
Hepsini birbiriyle karşılaştırmaya gerek olmaması lazım. tankları ve sıvıları hacmine göre sıraladım.
Sıra ile ilerleyip En küçük tanka elimdeki en büyük sıvıyı sokmaya çalışarak ilerledim. böylece hepsi oturması gereken yerlere oturdu.
Eğer hesabımda hata varsa muhtemelen volume, birim hatalarından kaynaklıdır diye düşünüyorum.
hocam bu algoritmada hata var yalniz.
elimizde
20 30 ltlik su oldugunu
ve sirasiyla
20 30 lt alabilicek tankla sahip oldugumuzu dusunersek, anlattigina gore en buyuk suyu en kucuk tanktan baslayarak doldurmaya calisiyosun. fakat gordugun gibi en kucukten baslayarak doldurmaya baslarsak 30 lt.lik tankin 10 lt lik kisminin doldugunu ve 20 ltlik sivinin elimizde kaldigini goruyoruz.
30 ltlik suyu once 20 ltlik tanka dolduruyoruz ve kalan 10 lt yi de 30 ltlik tanka dolduruyoruz. yani 30 ltlik tankinda 10 lt si doluyor. sivilar karisamayacagi icin de elimizde 20 ltlik sivi kaliyor.
halbuki olmasi gereken
20 ltlik suyun 20 ltlik tanka
30 ltlik suyun ise 30 ltlik tanka doldurulmasi ve elimizde hic suyun kalmamasi.
yani bu sorunun heuristic bi cevaptan fazlasina sahip olmasi icin butun permutasyonlarin denenmesi gerekiyor.
-
guru:
yok hocam ben orda fazla özet geçtim. ordaki iş daha karmaşık.
Ben hala bütün permütasyonların denenmesinin gerkmediğini düşünüyorum. Çünkü kaplar ve sıvılar hacme göre sıralı.
İlk aşamada her sıvı büyükten küçüğe girebileceği en küçük kaba girmeye çalışıyor.
Ondan sonra arta kalan sıvılar benzer mantıkla tekrar yerleşiyor (burada ufak bi verimsizlik olabilir yada bu aşamada sıvıdan 1 gram artınca tekrar sort etmek gerekebilir belki )
zande:
ne C++ 'ı hacım ? hayatından mı bezdin ne uğraşacan, o şey 2000 satır olur C++ da.
Şu aşamada çıktısı gayet verimli görünüyor
TANKLARIN ICINDEKI TOPLAM HACIM: 13005,2
HolyOne tarafından 05/Ağu/13 17:53 tarihinde düzenlenmiştir
TOPLAM SIVI HACMI: 12316,5764972863
TANKLARIN ICINDEKI TOPLAM SIVI HACMI: 12258,3296618433
-----Bosta kalan (hicbir tanka girmeyen) sivilar----
Ethanol Size1090 Vol:1379,74683544304
Bosta kalan miktar:58,2468354430379 -
hocam yalnizca eklenen tanklari ve sulari verdigim ornekteki gibi duzenledim. ve gordugun gibi bosta kalan miktar 10
ancak 20 ve 30 lt alan tanklara 20 ve 30 lt iki ayri suyun aktarilmasi esitlenme ile sonuclanmaliydi. yani kalan miktarin 0 olmasi gerekiyodu.
senin yaklasimin heuristic bi yaklasim, yani evet guzel ama tam anlamiyla cevabi vericeginden hic bi zaman emin olamiyacagimiz bi algoritma
cevabindan tam anlamiyla emin olabilicegimiz bi algoritma icin ise, elimizde ki tanklarin permutasyonunu almamiz gerekiyor. ve tum permutasyonlari elde ederken de senin yaptigina benzer bi sekilde sivilari sirasiyla dizmeye calismaliyiz.
-
Abü kodu değiştirdiysen tüm tank ve liquidleri silmeseydin de sonuçları karşılaştırsaydık.
senin algoritman daha iyiyse adres ver geliorum :PPP
Hocam bulduğun hatanın sebebi şuymuş
Alttaki kod bloğuna bak onu > yapmışım ama >= olması gerekiyormuş, şimdi düzelttim olması gereken sonucu verdi.
if (Tanks[i].Liquid == null) //tankın içi boşsa
if (Tanks[i].Volume >= Liquids[j].Volume)
{
Tanks[i].Liquid = Liquids[j];
// bu sivinin isi bitti kullandik
Tanks[i].DoluOlanVolume = Liquids[j].Volume;
Liquids.RemoveAt(j);
break; // bu tankin isi bitti siradakine gecelim
} -
yok hocam oyle bi iddiam yok :) [ olay adres ver boyutundaysa :p ]
benim yazdigim kod parcasinin bununla da pek alakasi yok aslinda, yalnizca benzer oldugu icin yazdim
edit: alakasi yok derken soru da density cart curt gibi ayrintilar yok yani :)
guru tarafından 05/Ağu/13 19:39 tarihinde düzenlenmiştir -
=)))) Ya aslında benimde içimden hepsiyle karşılaştırma geçio da bütün denemelerimde doğru sonucu verdi. Eğer bi saçmalık var derse eleman bir daha üstünden geçerim çalışan bişi yaptım da en doğru yol olduğuna çok da emin değilim yani=) ama yinede iş görüyor olması lazım
-
guru hocam:
O değilde ben bunun 3d sine uzun zamandır kafa yoruyorum hiç onu düşündün mü?
Yani diyelim ki tank değil de bir depon var.
Depoda 10 tane büyük 5 tane dar alan var. bunlara da çeşitli en boy ve genişlikte kutuları yerleştirecen.
O zaman nasıl bir brute force çekmeyi planlarsın =)
-
HolyOne bunu yazdı
=)))) Ya aslında benimde içimden hepsiyle karşılaştırma geçio da bütün denemelerimde doğru sonucu verdi. Eğer bi saçmalık var derse eleman bir daha üstünden geçerim çalışan bişi yaptım da en doğru yol olduğuna çok da emin değilim yani=) ama yinede iş görüyor olması lazım
guru'nun dediği gibi tankların permütasyonlarında grup toplamına en yakın sıvı hacmine göre puanlama ile veya genetik seçilme yöntemiyle doğruya en yakın sonucu buldurabiliriz. ben biraz kastım yazmak için ama beceremedim. :)
muhtemelen bi algoritma yarışması sorusu ve güzelmiş :)
-
bütün ihtimalleri denemeye gerek yok diye biliyorum ben de geçen sene bir süre uğraşmıştım holy'ninkine benzer bir algoritma ile yapmıştım ödevi ben de. aslında algoritmanın adı da vardı ama şimdi aklıma gelmiyor. :/ 3 boyutlu olduğunda nasıl yapılır tam olarak bilmiyorum ama bir cismi kutuya koyduğunda cismin köşelere göre projeksiyonunu (yansımasını yani bir anlamda) alıp o 2 boyutlu veri üzerinde karşılaştırmalar yaparak çözülebilir gibi geliyor bana. ama burda en büyüğünü en küçüğe koy mantığı hiç işlemez çünkü şekiller çok çok farklı olabilir. :)