Algoritma problemi

hannibal1903

11 yıl (348 mesaj)

Teğmen

Konu Sahibi

N tane çocuk M tanede oyuncak var.Her oyuncağın mutluluk puanı var.Örneğin bir oyuncağın iki farklı çocuğu mutlu etme puanı farklı.Bu oyuncaklar çocuklara öyle dağıtılacakki mutluluk puanı en az olan mümkün olduğu kadar fazla puan alabilecek.Bir çocuğa birden fazla oyuncak verilebilir.ve Her çocuk oyuncak alacak.Bu dağıtma işlemini nasıl yapabiilirim.Fikirlerinizi bekliyorum.

DH forumlarında vakit geçirmekten keyif alıyor gibisin ancak giriş yapmadığını görüyoruz.

Üye olduğunda özel mesaj gönderebilir, beğendiğin konuları favorilerine ekleyip takibe alabilir ve daha önce gezdiğin konulara hızlıca erişebilirsin.

Üye Ol Şimdi Değil

Bir Daha Gösterme

< Bu mesaj bu kişi tarafından değiştirildi hannibal1903 -- 21 Kasım 2014; 14:09:02 >

L

lavara123

11 yıl (388 mesaj)

Yüzbaşı

mesela çocuklar: N1, N2, N3, N4, N5 olsun:
oyuncaklar: M1, M2, M3, M4, M5, M6, M7, M8, M9, M10 olsun.

Misal: N1. Çocuğu 1x ve 9+ oyuncakları en çok mutlu etsin yani N1. Çocuğu 1x = M1, 9+ = M10. Oyuncaklar en çok mutlu ediyor.
Bu durumda N2. Çocuğuda: 1x=M2, 7+ = M9. Mutlu etsin
N3. = M3, 5+=M8 .....

Sorunu pek anlayamadım ama benim anladığım yukardaki şekil

< Bu ileti mini sürüm kullanılarak atıldı >

M

Mephalay

11 yıl (5771 mesaj)

Yarbay

Her cocuk oyuncak alacak.
Oncelikle O(nm) complexity sinde bir algoritma ile her cocuk icin, o cocuga en fazla mutluluk veren oyuncagi ver.
Daha sonra kalan oyuncaklari da, O(m-n) complexity sinde bir algoritma ile , her oyuncagi en fazla mutluluk verecegi cocuga dagit. Total complexity O(mn) oluyor.
Eger java'da yapiyorsan Set Interface ini kullanabilirsin.

Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @hannibal1903

H

hannibal1903

11 yıl (348 mesaj)

Teğmen

Konu Sahibi

Ya bu algoritmaya göre en az mutluluk puanı olan çocuk mümkün olduğu kadar çok puan mı almış olacak @Mephalay

Bu mesaja 1 cevap geldi.

M

Mephalay

11 yıl (5771 mesaj)

Yarbay

quote:

Orijinalden alıntı: hannibal1903

Ya bu algoritmaya göre en az mutluluk puanı olan çocuk mümkün olduğu kadar çok puan mı almış olacak @Mephalay

Hayir, dagitilabilecek maksimum mutluluk puani dagitilacak. Cocuklarin hepsinin ilk basta mutluluk puani esit ve sifir degil mi?

< Bu ileti mobil sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

H

hannibal1903

11 yıl (348 mesaj)

Teğmen

Konu Sahibi

quote:

Orijinalden alıntı: Mephalay

quote:

Orijinalden alıntı: hannibal1903

Ya bu algoritmaya göre en az mutluluk puanı olan çocuk mümkün olduğu kadar çok puan mı almış olacak @Mephalay

Hayir, dagitilabilecek maksimum mutluluk puani dagitilacak. Cocuklarin hepsinin ilk basta mutluluk puani esit ve sifir degil mi?

İlk başta hiçbirinde oyuncak yok bu nedenle sıfır mutluluk puanları.Hiçbir oyuncak açıkta kalmayacak ve her çocuğa dağıtılacak.Ama mutluluk puanı az olan mümkün olduğunca büyük puan almaya çalışacak.Her çocuk farklı sayıda oyuncak alabilir.Anladınız deil mi sorumu??

Bu mesaja 1 cevap geldi.

M

Mephalay

11 yıl (5771 mesaj)

Yarbay

Simdi dediklerinde soyle bir problem var.
Eger herkesin basta puani 0 ise, "mutluluk puani az olan mumkun oldugunca buyuk puan almaya calisacak" demek aslinda "bir oyuncak, ona sahip olunca en fazla mutlu olacak olan cocuga verilmelidir" anlamina geliyor. Eger bu noktayi acikliga kavusturursak olay netlesecek : )
Yani soyle sorayim 3 tane cocuk var , hepsinde en az 1 tane oyuncak var ve mutluluk puanlari sirasiyla 3,4,5. Benim elimdeki son kalan oyuncagi dagitmak istiyorum. O oyuncagi cocuklara verirsem alacaklari mutluluk puanlari sirasiyla 6,7,8. Bu durumda ben, 8 puan alacagi icin mutluluk puani 5 olan cocuga vermeyi tercih edecegim ve sonuc olarak 3,4,13 mutluluk puani ile bitecek . Ancak sen diyorsun ki " mutluluk puani az olan mumkun oldugunca buyuk puan almaya calisacak " , yani bu durumda ben 3. cocuga vermektense sirf dusuk puanli oldugu icin 3'e mi vermeliyim ? Anlatabildim mi ?

< Bu mesaj bu kişi tarafından değiştirildi Mephalay -- 21 Kasım 2014; 0:25:10 >
Bu mesaja 2 cevap geldi.

Bu mesajda bahsedilenler: @hannibal1903

T

ThisisaNightmare

11 yıl (6694 mesaj)

Yarbay

Sorunu basta okudugumda knapsack gibi geldi fakat sorun surada: bir cocuk birsuru oyuncak alabiliyor ve her cocuga oyuncak dagitilacak. O zaman Mephalay in dedigi gibi O(mn) zamanda cozersin bu problemi.

H

hannibal1903

11 yıl (348 mesaj)

Teğmen

Konu Sahibi

quote:

Orijinalden alıntı: Mephalay

Simdi dediklerinde soyle bir problem var.
Eger herkesin basta puani 0 ise, "mutluluk puani az olan mumkun oldugunca buyuk puan almaya calisacak" demek aslinda "bir oyuncak, ona sahip olunca en fazla mutlu olacak olan cocuga verilmelidir" anlamina geliyor. Eger bu noktayi acikliga kavusturursak olay netlesecek : )
Yani soyle sorayim 3 tane cocuk var , hepsinde en az 1 tane oyuncak var ve mutluluk puanlari sirasiyla 3,4,5. Benim elimdeki son kalan oyuncagi dagitmak istiyorum. O oyuncagi cocuklara verirsem alacaklari mutluluk puanlari sirasiyla 6,7,8. Bu durumda ben, 8 puan alacagi icin mutluluk puani 5 olan cocuga vermeyi tercih edecegim ve sonuc olarak 3,4,13 mutluluk puani ile bitecek . Ancak sen diyorsun ki " mutluluk puani az olan mumkun oldugunca buyuk puan almaya calisacak " , yani bu durumda ben 3. cocuga vermektense sirf dusuk puanli oldugu icin 3'e mi vermeliyim ? Anlatabildim mi ?

Mutluluk puanı çocukla alakalı örneğiin 1 nolu oyuncak olsun. bu 1. çocuğu 3 mutlu ediyorsa aynı oyuncak 2. çocuğu atıyorum 5 mutlu etsin anlatabildim mi.Yani aynı oyuncağın farklı çocukları mutlu etme puanıda farklı.Ben bu oyuncakları öyle dağıtacağım ki çocuklara mutluluk puanı az olan mümkün olduğunda büyük olacak.Bunun için nasıl bir yol izlemek lazım onu soruyorum :) Bir örnekle açıklamak gerekirse 2 çocuk olsun 3 oyuncak olsun.1. çocuk için mutluluk puanları 2,3,4 olsun 2. çocuk için 1,5,6 olsun bu 3 oyuncağı 2 çocuğa nasıl dağıtacağız ki nasıl dağıtacağız ki mutluluk puanı toplamı az olan çocuk mümkün olduğınca büyük olacak.1. çocuk 1. ve 2. oyuncağı alırsa
2+3=5 mutluluk puanı olacak. 2. çocukta 3. oyuncağı alır bu durumda onunda mutluluk puanı 6 olur.

Bu mesaja 1 cevap geldi.

P

Perceptron

11 yıl (2806 mesaj)

Binbaşı

2 dimensional array ile mutluluk puanları ifade edilir.
N boyutlu array içindeki değişken boyutlu array ilede aldığı oyuncaklar.
Amacınız ne? her çocuğa toplam aynı mutluluk puanı mı düşmeli?

Bu mesaja 1 cevap geldi.

H

hannibal1903

11 yıl (348 mesaj)

Teğmen

Konu Sahibi

quote:

Orijinalden alıntı: .fcan

2 dimensional array ile mutluluk puanları ifade edilir.
N boyutlu array içindeki değişken boyutlu array ilede aldığı oyuncaklar.
Amacınız ne? her çocuğa toplam aynı mutluluk puanı mı düşmeli?

Her çocuğa aynı mutluluk puanı düşmeyecek.Mutluluk puanı az olan mümkün olduğunca büyük olacak.Yani mutluluk puanları dengeli olacak bir nevi..