2016-05-06 92 views
5

我在本地社區學院學習了Java類的數據結構和算法,並且完全停留在當前的作業上。問題如下...貪婪算法Java/firstFit方法

編寫一個程序,將不同重量的對象打包到容器中。每個容器可以容納最多10磅。

該程序使用貪婪算法,將一個對象放入它適合的第一個bin中。

我不是要求我爲我做功課,我只是真的希望指出正確的方向。我的程序真的很接近工作,但我無法讓它正常工作。我能夠得到第一個容器來保持適量的重量,但之後,其餘的容器只能保持每個容器一個重量值。以下是我迄今爲止....

import java.util.ArrayList; 


public class Lab20 { 
    public static void main(String[] args) { 
     final java.util.Scanner input = new java.util.Scanner(System.in); 

    System.out.print("Enter the number of objects: "); 
    double[] items = new double[input.nextInt()]; 
    System.out.print("Enter the weight of the objects: "); 
    for (int i = 0; i < items.length; i++) { 
     items[i] = input.nextDouble(); 
    } 

    ArrayList<Bin> containers = firstFit(items); 

    //Display results 
    for (int i = 0; i < containers.size(); i++) { 
     System.out.println("Container " + (i + 1) 
       + " contains objects with weight " + containers.get(i)); 
    } 
    input.close(); 
} 

//Greedy Algorithm?? 
public static ArrayList<Bin> firstFit(double[] items) { 
    ArrayList<Bin> list = new ArrayList<>(); 
    Bin bin = new Bin(); 

    list.add(bin); 

    for (int i = 0; i < items.length; i++) { 
     if (!bin.addItem(items[i])) { 
      Bin bin2 = new Bin(); 
      list.add(bin2); 
      bin2.addItem(items[i]); 
      } 
     } 
     return list; 
    } 
} 

//Bin Class 
class Bin { 
    private ArrayList<Double> objects = new ArrayList<>(); 
    private double maxWeight = 10; 
    private double totalWeight = 0; 

    public Bin() { 
    } 

    public Bin(double maxWeight) { 
     this.maxWeight = maxWeight; 
    } 

    //Or is this supposed to be the Greedy algorithm?? 
    public boolean addItem(double weight) { 
     if ((totalWeight+weight) <= maxWeight) { 
      objects.add(weight); 
      totalWeight += weight; 
      return true; 
     } 
     else { 
      return false; 
     } 
    } 

    public int getNumberOfObjects() { 
     return objects.size(); 
    } 

    @Override 
    public String toString() { 
     return objects.toString(); 
    } 
} 

這裏是我得到的輸出...

輸入對象的數量:6

輸入的重量對象:7 5 2 3 5 8

容器1包含具有重量[7.0,2.0]

容器2包含重量對象的對象[5.0]

容器3含有具有重量的物體[3.0]

容器4包含具有重量的物體[5.0]

容器5包含具有重量的物體[8.0]


而這就是在輸出應該是...

輸入對象的數量:6

進入重量的對象:7 5 2 3 5 8

容器1包含有重量[7.0,2.0]

容器2包含重量對象的對象[5.0,3.0]

容器3含有與對象重量[5.0]

容器4包含重量[8.0]

回答

3

有在firstFit方法中的問題的對象。

你要做的是,你只嘗試添加一個元素到BinList中的第一個bin。爲了達到您的期望,您必須嘗試將該項目添加到列表中的所有倉位。然後你應該檢查你是否可以添加或不添加。如果沒有,你必須使用一個新的bin並按如下所示添加到列表中。

for (int i = 0; i < items.length; i++) { 
    boolean added=false;  
    for(Bin bin: list){ 
     if(bin.addItem(items[i])){ 
      added=true;   
      break; 
     } 
    } 
    if(!added){ 
     Bin bin=new Bin(); 
     bin.addItem(items[i]); 
     list.add(bin); 
    } 
} 
return list; 
+0

您可以通過使用帶標籤的continue items_loop;而不是break來直接進入外循環的下一次迭代來擺脫'added'變量。 – Thilo