Ya Bu Soru İçin Bi Algoritması Olan Var Mı ???

Tahribat.com Forumları
line

C - C++

Ya Bu Soru İçin Bi Algoritması Olan Var Mı ???

22/Tem/09 05:54 Kısayol Şikayet Özel Mesaj

JUSTICE

Kayıt Tarihi: 08/Eylül/2007

Çözüm kesin knapsack ama hatırlayamadım bir türlü. Bir bakıyım cevabını yazcam inş.

Alıntı yap
22/Tem/09 11:04 Kısayol Şikayet Özel Mesaj

Kreston

Kayıt Tarihi: 28/Aralık/2002

Verilen her eşya değerini 2 ye bölüyorum. eğer küsüratlı sayı çıkarsa birinde floor yapıyorum(0 a yakın olan değeri alıyorum) diğerinde ceil yapıyorum(sonsuza yakın olan değerini alıyorum) topluyorum eşya değerlerini
48 buluyorum. Burdan gidebilirsin belki çok basit oldu algoritma ama bi kaç değişiklikle istediğin şey olabilir.
edit : hatta ne diye uğraşıcan ki topla bütün değerleri böl 2ye tam sayı çıkarsa bir eksilt onu S yap. bir ekle onu da G yap o kadar. Küsüratlı çıkarsa da yuvarlayıp yap

Zimbabwe

Alıntı yap
10/Ağu/09 16:06 Kısayol Şikayet Özel Mesaj
guru

Kayıt Tarihi: 30/Mart/2007
.yillarin konusunu hortlattigim icin kendimden utaniyorum ama :) yine gecen gun bi arkadasima bu soruyu sordum ve aklima degisik bi cozum geldi. yani butun ihtimalleri deneme konusunda binary aritmetiginden faydalanmak. recursive beklenen cozum yerine farkli bi yaklasim oldugu icin paylasiyorum.

kisaca anlatmak gerekirse, bir bit mirasin kime ait oldugunu belli edicek. 1 ise miras, ismi m harfi ile baslayan arkadasin, 0 ise miras, g ile baslayan arkadasin olucak. eger elimizde iki miras urunu varsa, iki bit'e ihtiyacimiz olucak ve bu yuzden iki bit'in ikisinin de bir oldugu konumu kendimize sinir olarak belirliyoruz. yani 1 biti o kadar oteliyoruz. ve sayimizi 0 dan baslatip sinira kadar ilerletiyoruz. bu sirada da tum olasiklar karsimiza dokuluyo.

0 0 :: ikiside m'de (0, ilk durum)
0 1 :: sagdaki g de, solda ki m de (1, ikinci durum)
1 0 :: soldaki g de, sagda ki m de (2, ucuncu durum)
1 1 :: ikiside g de (3, son durum)
```
#include <stdio.h>

#define ARRAYSIZE(arr) ( sizeof((arr)) / sizeof((*arr)) )

void show_psb(size_t *arr, size_t n)
{
	unsigned long long i, j, rn;
	
	// iki arkadasin degiskenleri :]
	size_t m, g;
	
	rn = 1 << (n);
	
	// i her artimda istedigimiz alt yapiyi bize saglar.
	// iki tabaninda islem yaptigimizda neler oldugunu sende biliyosun zaten
	// rn kontrol degiskeni ;)
	// j diziyi dolassin diye var 
	
	for (i = 0; i < rn; ++i) {
		for (g = m = 0, j = 0; j < n; ++j) {
			// siradaki miras kimin ?
			if ( (i >> j) & 1 )
				m += arr[j];
			else 
				g += arr[j];
				
			printf("(%c %zu) ", (i >> j) & 1 ? 'm' : 'g', arr[j]);
		}
		printf(":: m:%zu g:%zu", m, g);
		putchar('\n');
	}
}

int main(int argc, char *argv[])
{
	size_t values[] = {1, 2, 3};
	show_psb(values, ARRAYSIZE(values));
}
```
guru tarafından 06/Ağu/13 20:30 tarihinde düzenlenmiştir

..
Alıntı yap

Toplam Hit: 5549 Toplam Mesaj: 24

Cevapla