Burada sırt çantası bir kap veya çanta gibidir. Diyelim ki, bazı ağırlıkları veya kazançları olan bazı eşyalar verdik. Bazı eşyaları sırt çantamıza toplam değer maksimum kâr sağlayacak şekilde koymalıyız.

Örneğin kabın ağırlığı 20 kg'dır. Eşyaları öyle bir şekilde seçmeliyiz ki, eşyaların ağırlıklarının toplamı kabın ağırlığından küçük ya da ona eşit olsun, kar maksimum olsun.

İki tür sırt çantası sorunu vardır:

• 0/1 sırt çantası sorunu
• Kesirli sırt çantası sorunu

Her iki sorunu da tek tek ele alacağız. Öncelikle 0/1 sırt çantası problemini öğreneceğiz.

0/1 sırt çantası problemi nedir?

0/1 sırt çantası problemi, sırt çantasına eşyaların ya tamamen doldurulması ya da hiç eşya doldurulmaması anlamına gelir. Örneğin, sırasıyla 2 kg ve 3 kg ağırlığa sahip iki öğemiz var. Eğer 2 kg'lık ürünü seçersek, 2 kg'lık üründen 1 kg'lık ürünü seçemeyiz (öğe bölünemez); 2kg'lık ürünü tamamen seçmeliyiz. Bu, ya öğeyi tamamen seçeceğimiz ya da öğeyi seçeceğimiz 0/1 sırt çantası problemidir. 0/1 sırt çantası problemi dinamik programlama ile çözülmüştür.

Kesirli sırt çantası problemi nedir?

Kesirli sırt çantası problemi, eşyayı bölebileceğimiz anlamına gelir. Örneğin 3 kg'lık bir eşyamız var, sonra 2 kg'lık eşyayı seçip 1 kg'lık eşyayı bırakabiliriz. Kesirli sırt çantası sorunu Açgözlü yaklaşımla çözülür.

0/1 sırt çantası problemine örnek.

Ağırlık ve kar sorununun şöyle olduğunu düşünün:

Ağırlıklar: {3, 4, 6, 5}

Kârlar: {2, 3, 1, 4}

Sırt çantasının ağırlığı 8 kg'dır

Öğe sayısı 4

Yukarıdaki sorun aşağıdaki yöntem kullanılarak çözülebilir:

X_Ben= {1, 0, 0, 1}

= {0, 0, 0, 1}

veritabanı java'yı bağlayın

= {0, 1, 0, 1}

Yukarıdakiler olası kombinasyonlardır. 1 öğenin tamamen çekildiğini, 0 ise hiçbir öğenin seçilmediğini gösterir. 4 öğe olduğundan olası kombinasyonlar şöyle olacaktır:

2⁴= 16; Bu yüzden. Yukarıdaki problem kullanılarak yapılabilecek 16 olası kombinasyon vardır. Tüm kombinasyonlar yapıldıktan sonra maksimum karı sağlayacak kombinasyonu seçmeliyiz.

Sorunun çözümüne yönelik bir diğer yaklaşım ise dinamik programlama yaklaşımıdır. Dinamik programlama yaklaşımında, karmaşık problem alt problemlere bölünür, daha sonra bir alt problemin çözümü bulunur ve alt problemin çözümü, karmaşık bir problemin çözümünü bulmak için kullanılır.

Dinamik programlama yaklaşımı kullanılarak bu sorun nasıl çözülebilir?

Birinci,

aşağıda gösterilen bir matris oluşturuyoruz:

Yukarıdaki matriste sütunlar ağırlığı, yani 8'i temsil eder. Satırlar, kalemlerin kârını ve ağırlıklarını temsil eder. Burada doğrudan 8'in ağırlığını almadık, problem alt problemlere bölünmüştür, yani 0, 1, 2, 3, 4, 5, 6, 7, 8. Alt problemlerin çözümü, hücreler ve sorunun cevabı son hücrede saklanacaktır. Öncelikle ağırlıkları büyükten küçüğe doğru yazıyoruz ve ağırlıklarına göre karları aşağıda gösterildiği gibi yazıyoruz:

İçinde_Ben= {3, 4, 5, 6}

P_Ben= {2, 3, 4, 1}

w=0 için öğe olmadığından ilk satır ve ilk sütun 0 olacaktır.

i=1 olduğunda, W=1

İçinde₁= 3; Sette ağırlığı 3 olan tek bir parçamız olduğundan sırt çantasının kapasitesi 1'dir. 3 kg'lık parçayı 1 kg kapasiteli sırt çantasına dolduramıyoruz, bu nedenle aşağıda gösterilen M[1][1]'e 0 ekleyin. :

i = 1 olduğunda, W = 2

İçinde₁= 3; Sette ağırlığı 3 olan tek bir parçamız olduğundan sırt çantasının kapasitesi 2'dir. 3 kg'lık parçayı 2 kg kapasiteli sırt çantasına dolduramıyoruz, bu nedenle aşağıda gösterilen M[1] [2]'ye 0 ekleyin. :

i=1 olduğunda, W=3

İçinde₁= 3; Sette ağırlığı 3 olan tek parçamız olduğundan ve sırt çantasının ağırlığı da 3 olduğundan; bu nedenle sırt çantasını ağırlığı 3'e eşit olan bir öğeyle doldurabiliriz. Aşağıda gösterilen M[1] [3]'e 3, yani 2 ağırlığına karşılık gelen karı koyarız:

i=1 olduğunda, W = 4

_W1= 3; Sette ağırlığı 3 olan tek parçamız olduğundan ve sırt çantasının ağırlığı da 4 olduğundan; bu nedenle sırt çantasını ağırlığı 3'e eşit olan bir öğeyle doldurabiliriz. Aşağıda gösterilen M[1] [4]'e 3, yani 2 ağırlığına karşılık gelen karı koyarız:

i=1 olduğunda, W = 5

_W1= 3; Sette ağırlığı 3 olan tek parçamız olduğundan ve sırt çantasının ağırlığı da 5 olduğundan; bu nedenle sırt çantasını ağırlığı 3'e eşit olan bir öğeyle doldurabiliriz. Aşağıda gösterilen M[1] [5]'e 3, yani 2 ağırlığına karşılık gelen karı koyarız:

i =1 olduğunda, W=6

_W1= 3; Sette ağırlığı 3 olan tek parçamız olduğundan ve sırt çantasının ağırlığı da 6 olduğundan; bu nedenle sırt çantasını ağırlığı 3'e eşit olan bir öğeyle doldurabiliriz. Aşağıda gösterilen M[1] [6]'ya 3, yani 2 ağırlığına karşılık gelen karı koyarız:

i=1 olduğunda, W = 7

_W1= 3; Sette ağırlığı 3 olan tek parçamız olduğundan ve sırt çantasının ağırlığı da 7 olduğundan; bu nedenle sırt çantasını ağırlığı 3'e eşit olan bir öğeyle doldurabiliriz. Aşağıda gösterilen M[1] [7]'ye 3, yani 2 ağırlığına karşılık gelen karı koyarız:

i =1 olduğunda, W =8

_W1= 3; Sette ağırlığı 3 olan tek parçamız olduğundan ve sırt çantasının ağırlığı da 8 olduğundan; bu nedenle sırt çantasını ağırlığı 3'e eşit olan bir öğeyle doldurabiliriz. Aşağıda gösterilen M[1] [8]'e 3, yani 2 ağırlığına karşılık gelen karı koyarız:

Şimdi 'i'nin değeri artırılıyor ve 2 oluyor.

i =2 olduğunda, W = 1

2 değerine karşılık gelen ağırlık 4'tür, yani w₂= 4. Kümede ağırlığı 4'e eşit olan tek bir öğemiz olduğundan ve sırt çantasının ağırlığı 1 olduğundan, ağırlığı 4 olan öğeyi bir sırt çantasına koyamayız, bu nedenle M[2][1'e 0 ekleriz. ] aşağıda gösterildiği gibi:

i =2 olduğunda, W = 2

2 değerine karşılık gelen ağırlık 4'tür, yani w₂= 4. Kümede ağırlığı 4'e eşit olan tek bir öğemiz olduğundan ve sırt çantasının ağırlığı 2 olduğundan, ağırlığı 4 olan öğeyi bir sırt çantasına koyamayız, bu nedenle M[2][2'ye 0 ekleriz. ] aşağıda gösterildiği gibi:

i =2 olduğunda, W = 3

2 değerine karşılık gelen ağırlık 4'tür, yani w₂= 4. Kümede ağırlıkları 3 ve 4 olan iki öğemiz olduğundan ve sırt çantasının ağırlığı 3 olduğundan, ağırlığı 3 olan öğeyi bir sırt çantasına koyabiliriz, bu nedenle M[2][3]'e 2 ekleriz. aşağıdaki gibi gösterilmiştir:

i =2 olduğunda, W = 4

2 değerine karşılık gelen ağırlık 4'tür, yani w₂= 4. Kümede ağırlıkları 3 ve 4 olan iki eşyamız olduğundan ve sırt çantasının ağırlığı 4 olduğuna göre. 4 ağırlığındaki eşyayı bir sırt çantasına koyabiliriz çünkü 4 ağırlığına karşılık gelen kazanç, ağırlığı olan eşyadan daha fazladır. 3'e göre aşağıda gösterildiği gibi M[2][4]'e 3 ekliyoruz:

i = 2 olduğunda, W = 5

2 değerine karşılık gelen ağırlık 4'tür, yani w₂= 4. Kümede ağırlıkları 3 ve 4 olan iki öğemiz olduğundan ve sırt çantasının ağırlığı 5 olduğuna göre, 4 ağırlığındaki öğeyi bir sırt çantasına koyabiliriz ve ağırlığa karşılık gelen kar 3 olur, dolayısıyla 3 ekleriz. M[2][5] aşağıda gösterildiği gibi:

i = 2 olduğunda, W = 6

2 değerine karşılık gelen ağırlık 4'tür, yani w₂= 4. Kümede ağırlıkları 3 ve 4 olan iki öğemiz olduğundan ve sırt çantasının ağırlığı 6 olduğuna göre, ağırlığı 4 olan öğeyi bir sırt çantasına koyabiliriz ve ağırlığa karşılık gelen kar 3 olur, dolayısıyla 3 ekleriz. M[2][6] aşağıda gösterildiği gibi:

i = 2 olduğunda, W = 7

2 değerine karşılık gelen ağırlık 4'tür, yani w₂= 4. Kümede ağırlıkları 3 ve 4 olan iki öğemiz olduğuna ve sırt çantasının ağırlığı 7 olduğuna göre. 4 ve 3 numaralı öğeleri bir sırt çantasına koyabiliriz ve ağırlıklara karşılık gelen kar 2 ve 3 olur; bu nedenle toplam kâr 5'tir, dolayısıyla aşağıda gösterildiği gibi M[2][7]'ye 5 ekliyoruz:

i = 2 olduğunda, W = 8

2 değerine karşılık gelen ağırlık 4'tür, yani w₂= 4. Kümede ağırlıkları 3 ve 4 olan iki öğemiz olduğuna ve sırt çantasının ağırlığı 7 olduğuna göre. 4 ve 3 numaralı öğeleri bir sırt çantasına koyabiliriz ve ağırlıklara karşılık gelen kar 2 ve 3 olur; bu nedenle toplam kâr 5'tir, dolayısıyla aşağıda gösterildiği gibi M[2][7]'ye 5 ekliyoruz:

Artık 'i'nin değeri artırılıyor ve 3 oluyor.

i = 3 olduğunda, W = 1

java ayy kavramları

3 değerine karşılık gelen ağırlık 5'tir, yani w₃= 5. Kümede ağırlıkları 3, 4 ve 5 olan üç öğemiz olduğundan ve sırt çantasının ağırlığı 1 olduğundan, öğelerin hiçbirini sırt çantasına koyamayız, bu nedenle M[3]['e 0 ekleriz[3] 1] aşağıda gösterildiği gibi:

i = 3 olduğunda, W = 2

3 değerine karşılık gelen ağırlık 5'tir, yani w₃= 5. Kümede ağırlıkları 3, 4 ve 5 olan üç öğemiz olduğundan ve sırt çantasının ağırlığı 1 olduğundan, öğelerin hiçbirini sırt çantasına koyamayız, bu nedenle M[3]['e 0 ekleriz[3] 2] aşağıda gösterildiği gibi:

i = 3 olduğunda, W = 3

3 değerine karşılık gelen ağırlık 5'tir, yani w₃= 5. Ağırlık kümesinde sırasıyla 3, 4 ve 5 olmak üzere üç adet eşyamız olduğuna ve sırt çantasının ağırlığı 3 olduğuna göre, ağırlığı 3 olan eşya sırt çantasına konulabileceğinden ve eşyaya karşılık gelen kar 2 olacağından, bu nedenle aşağıda gösterildiği gibi M[3][3]'e 2 ekliyoruz:

i = 3 olduğunda, W = 4

3 değerine karşılık gelen ağırlık 5'tir, yani w₃= 5. Ağırlık kümesinde sırasıyla 3, 4 ve 5'lik üç öğemiz olduğundan ve sırt çantasının ağırlığı 4 olduğundan, ağırlığı 3 veya 4 olan öğeyi tutabiliriz; 4 ağırlığına karşılık gelen kâr (3), 3 ağırlığına karşılık gelen kârdan daha fazladır, bu nedenle aşağıda gösterilen M[3][4]'e 3 ekleriz:

i = 3 olduğunda, W = 5

3 değerine karşılık gelen ağırlık 5'tir, yani w₃= 5. Ağırlık kümesinde sırasıyla 3, 4 ve 5 olan üç öğemiz olduğundan ve sırt çantasının ağırlığı 5 olduğundan, ağırlık kümesindeki öğeyi 3, 4 veya 5 olarak tutabiliriz; 4 ağırlığına karşılık gelen kâr (3), 3 ve 5 ağırlığına karşılık gelen kârdan daha fazladır, bu nedenle aşağıda gösterilen M[3][5]'e 3 ekleriz:

i =3 olduğunda, W = 6

3 değerine karşılık gelen ağırlık 5'tir, yani w₃= 5. Ağırlık kümesinde sırasıyla 3, 4 ve 5'lik üç öğemiz olduğundan ve sırt çantasının ağırlığı 6 olduğundan, ağırlığı 3, 4 veya 5 olan öğeyi tutabiliriz; 4 ağırlığına karşılık gelen kâr (3), 3 ve 5 ağırlığına karşılık gelen kârdan daha fazladır, bu nedenle aşağıda gösterilen M[3][6]'ya 3 ekleriz:

i =3 olduğunda, W = 7

3 değerine karşılık gelen ağırlık 5'tir, yani w₃= 5. Ağırlık kümesinde sırasıyla 3, 4 ve 5 olmak üzere üç öğemiz olduğundan ve sırt çantasının ağırlığı 7 olduğundan, bu durumda hem ağırlık 3 hem de 4 olan öğeleri tutabiliriz, yani kârın toplamı (2 + 3), yani 5'e eşit olacaktır, dolayısıyla aşağıda gösterildiği gibi M[3][7]'ye 5 ekliyoruz:

i = 3 olduğunda, W = 8

Linux dosya sistemi

3 değerine karşılık gelen ağırlık 5'tir, yani w₃= 5. Ağırlık kümesinde sırasıyla 3, 4 ve 5 olmak üzere üç öğemiz olduğundan ve sırt çantasının ağırlığı 8 olduğundan, bu durumda ağırlıkları 3 ve 4 olan öğelerin toplamı tutabiliriz. kâr (2 + 3), yani 5'e eşit olacaktır, dolayısıyla aşağıda gösterildiği gibi M[3][8]'e 5 ekliyoruz:

Artık 'i'nin değeri artırılarak 4 olur.

i = 4 olduğunda, W = 1

4 değerine karşılık gelen ağırlık 6'dır, yani w₄= 6. Ağırlık kümesinde sırasıyla 3, 4, 5 ve 6 olmak üzere dört öğemiz olduğundan ve sırt çantasının ağırlığı 1 olduğundan. Tüm öğelerin ağırlığı sırt çantasının ağırlığından daha fazladır, dolayısıyla yapamayız sırt çantasına herhangi bir öğe ekleyin; Bu nedenle, aşağıda gösterildiği gibi M[4][1]'e 0 ekliyoruz:

i = 4 olduğunda, W = 2

4 değerine karşılık gelen ağırlık 6'dır, yani w₄= 6. Ağırlık kümesinde sırasıyla 3, 4, 5 ve 6 olmak üzere dört öğemiz olduğundan ve sırt çantasının ağırlığı 2 olduğundan. Tüm öğelerin ağırlığı sırt çantasının ağırlığından daha fazladır, dolayısıyla yapamayız sırt çantasına herhangi bir öğe ekleyin; Bu nedenle, aşağıda gösterildiği gibi M[4][2]'ye 0 ekliyoruz:

i = 4 olduğunda, W = 3

4 değerine karşılık gelen ağırlık 6'dır, yani w₄= 6. Sırasıyla 3, 4, 5 ve 6 ağırlık kümesinde dört öğemiz olduğundan ve sırt çantasının ağırlığı 3 olduğundan. Ağırlığı 3 olan öğe sırt çantasına konulabilir ve buna karşılık gelen kar ağırlık 4, 2'dir, dolayısıyla aşağıda gösterildiği gibi M[4][3]'e 2 ekleyeceğiz:

i = 4 olduğunda, W = 4

4 değerine karşılık gelen ağırlık 6'dır, yani w₄= 6. Sırasıyla 3, 4, 5 ve 6 ağırlık kümesinde dört öğemiz olduğundan ve sırt çantasının ağırlığı 4 olduğundan. Ağırlığı 4 olan öğe sırt çantasına konulabilir ve buna karşılık gelen kar ağırlık 4, 3'tür, dolayısıyla aşağıda gösterildiği gibi M[4][4]'e 3 ekleyeceğiz:

i = 4 olduğunda, W = 5

4 değerine karşılık gelen ağırlık 6'dır, yani w₄= 6. Sırasıyla 3, 4, 5 ve 6 ağırlık kümesinde dört öğemiz olduğundan ve sırt çantasının ağırlığı 5 olduğundan. Ağırlığı 4 olan öğe sırt çantasına konulabilir ve buna karşılık gelen kar ağırlık 4, 3'tür, dolayısıyla aşağıda gösterildiği gibi M[4][5]'e 3 ekleyeceğiz:

i = 4 olduğunda, W = 6

4 değerine karşılık gelen ağırlık 6'dır, yani w₄= 6. Ağırlık kümesinde sırasıyla 3, 4, 5 ve 6 olan dört öğemiz olduğundan ve sırt çantasının ağırlığı 6 olduğundan. Bu durumda öğeleri sırt çantasına ağırlıkları 3, 4 olan herhangi birinden koyabiliriz. , 5 veya 6 ama kar, yani 4 ağırlığına karşılık gelen 6, tüm kalemler arasında en yüksek olanıdır; bu nedenle aşağıda gösterildiği gibi M[4][6]'ya 4 ekliyoruz:

i = 4 olduğunda, W = 7

4 değerine karşılık gelen ağırlık 6'dır, yani w₄= 6. Ağırlık kümesinde sırasıyla 3, 4, 5 ve 6 dört öğemiz olduğundan ve sırt çantasının ağırlığı 7 olduğundan. Burada, ağırlığı 3 ve 4 olan iki öğeyi eklersek o zaman maksimumu üretecektir kâr, yani (2 + 3) 5'e eşit olduğundan, aşağıda gösterildiği gibi M[4][7]'ye 5 ekliyoruz:

i = 4 olduğunda, W = 8

4 değerine karşılık gelen ağırlık 6'dır, yani w₄= 6. Ağırlık kümesinde sırasıyla 3, 4, 5 ve 6 dört öğemiz olduğundan ve sırt çantasının ağırlığı 8 olduğundan. Burada, ağırlığı 3 ve 4 olan iki öğeyi eklersek o zaman maksimumu üretecektir kâr, yani (2 + 3) 5'e eşit olduğundan, aşağıda gösterildiği gibi M[4][8]'de 5 ekliyoruz:

Yukarıdaki tabloda gördüğümüz gibi tüm girişler arasında maksimum kazanç 5'tir. İşaretçi 5 değerine sahip son satırı ve son sütunu işaret eder. Şimdi 5 değerini önceki satırla karşılaştıracağız; önceki satır, yani i = 3 aynı 5 değerini içeriyorsa işaretçi yukarı doğru kayar. Önceki satır 5 değerini içerdiğinden işaretçi aşağıdaki tabloda gösterildiği gibi yukarı kaydırılacaktır:

Yine yukarıdaki satırdaki 5 değerini karşılaştıracağız, yani i = 2. Yukarıdaki satır 5 değerini içerdiğinden işaretçi aşağıdaki tabloda gösterildiği gibi tekrar yukarı kaydırılacaktır:

Yine yukarıdaki satırdaki 5 değerini karşılaştıracağız, yani i = 1. Yukarıdaki satır aynı değeri içermediğinden, i=1 satırını dikkate alacağız ve satıra karşılık gelen ağırlık 4 olacaktır. Dolayısıyla 4 ağırlığını seçtik ve aşağıda gösterilen 5 ve 6 ağırlıklarını reddettik:

x = { 1, 0, 0}

Ağırlığa karşılık gelen kâr 3'tür. Dolayısıyla kalan kâr (5 - 3) 2'ye eşittir. Şimdi bu 2 değerini i = 2 satırıyla karşılaştıracağız. (i = 1) satırı 2 değerini içerdiğinden ; bu nedenle işaretçi aşağıda gösterildiği gibi yukarıya doğru kaydırılmıştır:

Yine 2 değerini yukarıdaki satırla, yani i = 1 ile karşılaştırıyoruz. i =0 satırı 2 değerini içermediğinden, i = 1 satırı seçilecek ve i = 1'e karşılık gelen ağırlık 3 olarak gösterilecektir. altında:

X = {1, 1, 0, 0}

Ağırlığa karşılık gelen kâr 2'dir. Dolayısıyla kalan kâr 0 olur. 0 değerini yukarıdaki satırla karşılaştırıyoruz. Yukarıdaki satır 0 değeri içerdiğinden ancak bu satıra karşılık gelen kâr 0'dır. Bu problemde karı maksimize etmek için 3 ve 4 olmak üzere iki ağırlık seçilir.