Siemka. Robię sobie ćwiczenie które jest wariantem "cutting stock rod problem" z algorytmów. Mam pobrać z linii poleceń cennik prętów (długość i cena) oraz projekt czyli zbiór odcinków prętów które mają zostać wykorzystane (wszystko posortowane rosnąco). Zadanie polega na takim doborze prętów z cennika aby zminimalizować odpad. Ilość prętów w cenniku jest nieograniczona. Wiem że najwydajniejszym sposobem jest wykonanie tego metodą programowania dynamicznego, ale na ten moment tego nie czaje. Robię to w inny sposób który teraz opiszę w punktach.
1.Generuję wszystkie możliwe podzbiory prętów z projektu takie w których suma elementów nie jest większa od najdłuższego pręta z cennika i zapisuje je w liście.
2.Tworzę tablicę w której zapisane są sumy elementów każdego z wygenerowanych zbiorów.
3.Tworzę metodę której przekazuję listę zbiorów i tablicę sum. W zewnętrznej iteruję po cenniku a w wewnętrznej po sumach. Wybieram najlepszy stosunek suma/pręt z cennika po czym kopiuję tablicę sum i listę podzbiorów i na tych kopiach wykonuję zerowanie wybranego ze stosunku suma/pręt z cennika elementu z tablicy sum i odpowiadających mu odcinków w liście podzbiorów. Wywołuję tę samą metodę pod koniec iteracji zewnętrznej pętli i przekazuje jej kopie sum i listę.Metoda jest zakończona gdy otrzyma wyzerowaną tablicę sum.
Wyobrażam sobie że ma to działać na takiej zasadzie że sprawdzę każdą możliwą kolejność wybierania prętów z cennika i dobiorę najlepsze zapełnienie które minimalizuje odpad.
Poniżej daję kod zakomentuję moment w którym wykryłem problem. Z góry dzięki za ewentualną pomoc lub sugestie co do metody rozwiązania.
public class Eco {
// List containing subsets generated based on set of rods in project.
List<int[]> subSets=new ArrayList<>();
private int[][] priceList;
public Eco(int[] project,int[][] List){
this.priceList=List;
generateSubstets(project);
List<int[]> sety=new ArrayList<>(this.subSets);
int[] sums=new int[sety.size()];
sums=setSums(sety,sums);
recursion(sums,sety);
}
int powTwo (int n){
int p=1;
while (n-->0) p+=p;
return p;
}
private void generateSubstets(int[] project){
int n=project.length;
int p=powTwo(n);
int longestRod=priceList[0][priceList[0].length-1];
int sum=0;
for(int i=1;i<p;i++){
int[] tab=new int[n];
for (int j=0;j<n;j++){
if((i & (1<<j))>0){
tab[j]=project[j];
sum=sum+project[j];
}
}
if (!(sum>longestRod)) {
subSets.add(tab);
}
sum=0;
}
}
int[] setSums(List<int[]> sets,int[] tab){
for (int j=0;j<tab.length;j++) {
if (!(tab[j]==0)){
tab[j]=0;
}
for (int i = 0; i <sets.get(0).length; i++) {
tab[j]=tab[j]+sets.get(j)[i];
}
}
return tab;
}
// Set new sums
List<int[]> refreshSets (List<int[]> sets,int[] tab){
for (int i=0;i<tab.length;i++){
if(tab[i]>0){
for (int[] temp:sets) {
temp[i]=0;
}
}
}
return sets;
}
private void recursion(int [] tab,List<int[]> list) {
if(!checkifNull(tab)){
return;
}
double ratio;
int index=0;
for (int j = 0; j < priceList[0].length; j++) {
ratio = 0;
// ratio ==0 zwróci jeśli obecny pręt z cennika jest niewystarczający do zapełnienia najmniejszej sumy z tablicy
for (int i = 0; i < tab.length; i++) {
if (ratio <= (double) tab[i] / priceList[0][j] & (double) tab[i] / priceList[0][j] <= 1.0 & (double) tab[i] > 0.0) {
ratio = (double) tab[i] / priceList[0][j];
index=i;
}
}
if (ratio==0) continue;
System.out.println(ratio + " " + priceList[0][j] + " " + tab[index] +" "+ index);
int[] copy=new int[tab.length];
List<int[]> listcopy=new ArrayList<>(list);
System.arraycopy(tab,0,copy,0,tab.length);
// Tutaj jak wykona się pierwsze całkowite wyzerowanie
// to metoda dalej już działa na wyzerowanej liście podzbiorów i tablicy, ale oryginale zmienne tab i list są ok.
// Podejrzewam że coś pomieszałem w rozumieniu przekazywania przez referencje.
listcopy=refreshSets(listcopy,listcopy.get(index));
copy=setSums(listcopy,copy);
recursion(Arrays.copyOf(copy,copy.length),new ArrayList<>(listcopy));
}
}
boolean checkifNull(int[] tab){
boolean check=false;
for (int i=0;i<tab.length;i++){
if(!(tab[i]==0)){
check=true;
}
}
return check;
}