Az zaman kaybı için algoritması gerek

[andelek]

Selam aleykum Arkadaslar!
Karsılaştıgım sorun isletmecilerin isi olabilir.
Ama algoritmasın bulmak gerek! Yardım ediniz...
 

Sizin elinizde n tane insan calisiyor diye düsünün.

n tane is aldiniz baska birisinden.Ve işçilerinize bir taneden is vermeniz  gerekir ki en az zaman karcansın.
Her işi işçiler farklı zamanlarda bitirebilirler.
Sizin amaciniz her işçiye bir iç yaptirın  toplam zaman en az olsun.

Işçilerin her iş için calisma zamanı matris seklinde  verilecektir.

Girdiler
n=3  (Iscilerin sayısı en cok 10 olabilir)

1-isci  90  50 20
2-isci  90  30  40
3-isci  5    4     3

Cıktı:

s=20+30+5=55

1-işçi 3 işçi 20 dakikada 2 -işçi ise 2 işi 30 dakikada 3-işci 1 işi 5 dakikada yapmislar.
(3-işci 3 işi daha az zamanda yapar ama o isi baskası yapmıstır)

Daha bir ornek

Girdi

n=2

1-isci 20 15
2-isci 16 14

Cıktı
  s=15+16=31 olur.

Eger s=20+14=34 olurdu. En az zamani bulmak icin s=15+16=31 i sectik.

Anlatabilirsem cok memnun olurum.

Yardımınızı bekliyorum.

[cellfish]

Tam olarak ne yapmaya calisdigini anlamadim.

Programin sonuc olarak ne yapmasi gerek, bunu aciklarsan yardimci olabilirim.

ayrica hangi dili kulaniyorsun?


cellfish

[cellfish]

Iscilerin saat ve zamani icin bu asadaki misali kulanbilirsin, C dilinde yapmisdim bunu. zaman fonksiyonunu:

Baslangic degerleri gosterip kaydet, saat icin ve takvim zamani icin. Bu asagida belirtdigim yontem ile:



simdi = saat() ;                           /* simdiki zamani al saatden */
takvim = zaman(NULL) ;            /* takivimdeki zamani al */

simdi ilmekle sayi zamanini calistiricak:

for( i=0L; i<sayi; i++)
{
   gecen = saat()-simdi)/SAAT_HER_SN ;
   if(gecen>=aralikli)
   {
      aralikli += 3;
      printf("\nGecen zaman = %ld saniye  iterasyon = %ld", gecen, i) ;
   }
}

Biseylerin oldugunu gostermek icin size ilmek ile cikis olarak gecen saati ve iterasyon sayisini gosteriyor, her 3 saniye.

Son olarak degerleri araliklari ile cikis olarak gostermek. (burda  saat()  ve  zaman()  kulaniyorum)

printf("\nCPU zamani %ld aralikli ise %.slf saniye\n",
         sayi, (double)(saat)-simdi)/SAAT_HER_SN ); 
printf("\nFinal saat zamani = %d Final takivim zamani = %d\n",
         saat(), zaman(NULL));
printf("\nGecen takvim zamani izletmek icin bu program %lf\n",
         degisiksaat(saat(NULL), takvim)) ;


Genelde  saat()  kulaniriz zamani hesaplamak icin, programi calistirdigimiz zaman icerisinde.

Bu C dilinde zaman fonksiyonunu misal olarak kulanabilirsin iscilerin girisi ve cikisi icin, tabi C dilinde biraz uzatiliyor ama ben bu dilde rahat oldugum icin bunu misal olarak veriyorum, Java da daha kolay yapilabilecek bir fonksiyon sanirim. takildigin yerler varsa arastir once, anlamadigin yerlerde burda sorabilirsin, arkadaslarin yardimci olicagindan eminim. En azindan bir sonuc cikartip buraya koyarsan yardimci olur herkes, ama burda kimse kimsenin odevini yapmaz, yapicagini da sanmiyorum.

cellfish

[andelek]

Sagolun arkadaşlar!
Sorunu anlatamayınca kendimi aptal gibi hissediyorum....

Kısaca açıklamak gerekirse

(nxn) Matrisımiz var.

Her sütünden ve her satırdan  bir tanaden alın ki onların toplamı en küçük olsun!

Örnek

(3x3) Matrisimiz verildi.

2 9 6   // Bu satirdan  2 'i sectik
3 8 4   //  Bu  satirdan 4 'u sectik
1 2 1   // Bu satirdan   2 ' 2 ' sectik

//  Satirlardan ve sutunlardan birden fazla eleman secemezsiniz!!!.
//  2<=n<=10 olabilir.
Sonuc:
En küçüğü = 2+4+2=8

Cikis yolunu gosterirseniz cok sevinirim...

[samety]

kullandığın sütunu silersin olur biter.matrisleri pek bilmiyorum ama ben bi kere dizi şeklinde bir matris olusturmustum eger matris dedigin oysa şu şekilde yaparsın
her secimden sonra
sectigin sütunu silersen bir sonrakinde o sütunu secemeyeceksin
verdigin örnekte
1. sutun   2. sütun   3.sütun
2             9             6   // Bu satirdan  2 'i sectik ve 1. sütunu sildik
3             8             4   //  Bu  satirdan 4 'u sectik ve 3. sütunu sildik
1             2             1   // Bu satirdan   2 ' 2 ' sectik ve 2. sütunu sildik



gibi olucak sectigin degerin sütununu sileceksin

[andelek]

Sagol arkadas. Dusundugun guzel,bu yontem de olur, ama asagidakileri bir okur musun?

2 9 6   
3 8 4   
1 2 1

Yukaridaki matriste sonuclar asagidaki gibi olur.

1) 2+8+1=11
2) 2+4+2=8
3) 3+9+1=13
4) 1+8+6=15
5) 6+3+2=11
6) 9+4+1=14

Bundan en kucugun secersek 8 olur.Anlatmak istedigim sey
Eger (10x10) olsa sonuclarin sayisi 10! olurdu. Secme ve silme islemlerinde de iterasyon sayisi
cok oluyor. Silme islemi ile bu seyi yapamiyoruz!(Time Limit: 500 ms )den fazla oluyor.!
Bu belki Graflarla cozulur diye dusunuyorum, daha dogrusu ne yapmayi bilmiyorum...

[samety]

neden olmasın !!
hesaplamayı nasıl yapıyorsun matristen veriyi nasıl çekiyorsun ?
Not: ben cok iyi değilim sadece biras programlama mantıgımla bişeyler yapmaya calısıorum.umarım yardımım dokunur