Algorytm plecakowy w Python'ie


Algorytm plecakowy to klasyczny przykład problemu analitycznego jaki próbuje się zrealizować w formie informatycznej, a który identyfikowany jest z klasycznym przykładem analizy inteligentnej.

Dla potrzeb problemu okreslane są:
- maksymalna dopuszczalna waga plecaka
- ilość przedmiotów, w tym ich waga i wartość

Celem algorytmu jest znalezienie optymalnej kombinacji przedmiotów, które łącznie nie przekroczą dopuszczalną ładowność plecaka, a osiągną maksymalną możliwą wartość.

import random
import pygame
import time
import random
import sys
import os
pygame.init()
black=[0,0,0]
white=[255,255,255]
green=[0,255,24]
screen = pygame.display.set_mode((1080,800))
pygame.display.set_caption("Algorytm plecakowy")
czcionka = pygame.font.SysFont("monospace", 30)
i=0
def buduj(n):
            res=[]
            for i in range(n):
                        res.append((i,1+int(9*random.random()),1+int(9*random.random())))                       
            return res
def powerset(items):
            res=[[]]
            for item in items:
                        newset=[r+[item] for r in res]
                        res.extend(newset)                        
            return res
def plecak_brute_force(items,max_weight):
            i=100
            plecak=[]
            best_wieght=0
            best_value=0
            for item_set in powerset(items):
                        set_weight=sum([e[1] for e in item_set])
                        set_value=sum([e[2] for e in item_set])
                        if set_value>best_value and set_weight<=max_weight:
                                    best_value=set_value
                                    best_weight=set_weight
                                    plecak = item_set
                                    pygame.draw.line(screen,white,(i,300),(i,300-best_weight),3)
                                    pygame.draw.line(screen,white,(i+10,300),(i+10,300+best_value),3)
                                    label = czcionka.render("waga= %.2f" %(best_weight), 1, green,white)
                                    screen.blit(label, (450, 10))
                                    label = czcionka.render("wartość= %.2f" %(best_value), 1, green,white)
                                    screen.blit(label, (450, 100))
                                    pygame.display.update()
                                    i=i+30
                                    time.sleep(1)
            return plecak, best_weight, best_value,i

                        

data=buduj(10)
print('data ',data)
max_w=20
pygame.draw.line(screen,white,(1,300),(1000,300),1)
pygame.draw.line(screen,green,(1,300-max_w),(1000,300-max_w),1)
label = czcionka.render("max waga= %.2f" %(max_w), 1, green,white)
screen.blit(label, (150, 10))
pygame.display.update()

pygame.display.update()
pl,opt_w,opt_v,i = plecak_brute_force(data,max_w)
print ('plecak ',pl)


pygame.draw.line(screen,green,(i,300),(i,300-opt_w),3)
pygame.draw.line(screen,green,(i+10,300),(i+10,300+opt_v),3)
label = czcionka.render("waga= %.2f" %(opt_w), 1, green,white)
screen.blit(label, (750, 10))
label = czcionka.render("wartość= %.2f" %(opt_v), 1, green,white)
screen.blit(label, (750, 100))
pygame.display.update()

Powyższy program wykorzystuje algorytm "brute Force".

Wyszukiwanie wyczerpujące (ang. exhaustive search), metoda siłowa (ang. brute force) – metoda polegająca na analizie wszystkich potencjalnych rozwiązań zadania w celu wybrania tego, które spełnia warunki zadania.
Złożoność obliczeniowa algorytmów realizujących wyszukiwanie wyczerpujące jest zazwyczaj bardzo duża, często wykładnicza. Metodę tę stosuje się do rozwiązywania problemów,
dla których znalezienie rozwiązania za pomocą innych dokładnych metod jest niemożliwe lub zbyt trudne.

Na poniszym zdjęciu można zaobserwować efekt pracy programu.



:)