Category

Algoritmi

Category

Introducere O problemă cu largă aplicabilitate practică, de la încărcarea mărfurilor în camioane și planificarea activităților până la amplasarea anunțurilor în pauzele publicitare. Problema rucsacurilor Dându-se un set \(I={1,…,n}\) de obiecte cu mărimi \(s_i \in (0, 1]\), și un set \(B={1,..,k}\) de cutii cu capacitatea 1, să se găsească o aranjare a obiectelor astfel încât numărul de cutii utilizat să fie minim. Formal, să se găsească o asociere \(a : I \rightarrow B\) astfel încât…

The first time I thought at this problem was when I worked on testing a component on a work-related project. Back then, I’ve realised that for properly testing the component, I should generate what seemed to be \(2^n\) distinct cases (n being the number of element types). \(2^n\)…odd coincidence or what? After some thought I realised this was a general answer, as these are the number of subset types that you can generate from a…