Beispielanalyse zur Implementierung des Rucksackalgorithmus in Java

Dieser Artikel stellt hauptsächlich eine kurze Einführung in die Implementierung des Rucksack-Algorithmus (0-1 Rucksack-Problem) in Java vor. Der Herausgeber findet ihn recht gut, daher werde ich ihn jetzt mit Ihnen teilen und als Referenz geben. Folgen wir dem Editor, um einen Blick darauf zu werfen

0-1-Knapsack-Problem

Das Knapsack-Problem ist ein NP-vollständiges Problem der kombinatorischen Optimierung. Das Problem kann wie folgt beschrieben werden: Bei einer gegebenen Menge von Artikeln hat jeder Artikel sein eigenes Gewicht und seinen eigenen Preis. Wie wählen wir innerhalb des begrenzten Gesamtgewichts aus, damit der Gesamtpreis der Artikel am höchsten ist? Der Name des Problems ergibt sich daraus, wie man den am besten geeigneten Gegenstand für einen bestimmten Rucksack auswählt.

Dies ist das grundlegendste Rucksackproblem. Seine Merkmale sind: Es gibt nur einen Gegenstand von jedem Typ, und Sie können wählen, ob Sie ihn hineinlegen möchten oder nicht.

Verwenden Sie Unterprobleme, um den Zustand zu definieren: Das heißt, f[i][v] stellt den Maximalwert dar, der erhalten werden kann, wenn die ersten i Gegenstände in einen Rucksack mit einer Kapazität von v gesteckt werden. Dann lautet seine Zustandsübergangsgleichung:

f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i ] }.

public class Bag {

  static class Item {// 定义一个物品
    String id; // 物品id
    int size = 0;// 物品所占空间
    int value = 0;// 物品价值

    static Item newItem(String id, int size, int value) {
      Item item = new Item();
      item.id = id;
      item.size = size;
      item.value = value;
      return item;
    }

    public String toString() {
      return this.id;
    }
  }

  static class OkBag { // 定义一个打包方式
    List<Item> Items = new ArrayList<Item>();// 包里的物品集合

    OkBag() {
    }

    int getValue() {// 包中物品的总价值
      int value = 0;
      for (Item item : Items) {
        value += item.value;
      }
      return value;
    };

    int getSize() {// 包中物品的总大小
      int size = 0;
      for (Item item : Items) {
        size += item.size;
      }
      return size;
    };

    public String toString() {
      return String.valueOf(this.getValue()) + " ";
    }
  }

  // 可放入包中的备选物品
  static Item[] sourceItems = { Item.newItem("4号球", 4, 5), Item.newItem("5号球", 5, 6), Item.newItem("6号球", 6, 7) };
  static int bagSize = 10; // 包的空间
  static int itemCount = sourceItems.length; // 物品的数量

  // 保存各种情况下的最优打包方式 第一维度为物品数量从0到itemCount,第二维度为包裹大小从0到bagSize
  static OkBag[][] okBags = new OkBag[itemCount + 1][bagSize + 1];

  static void init() {
    for (int i = 0; i < bagSize + 1; i++) {
      okBags[0][i] = new OkBag();
    }

    for (int i = 0; i < itemCount + 1; i++) {
      okBags[i][0] = new OkBag();
    }
  }

  static void doBag() {
    init();
    for (int iItem = 1; iItem <= itemCount; iItem++) {
      for (int curBagSize = 1; curBagSize <= bagSize; curBagSize++) {
        okBags[iItem][curBagSize] = new OkBag();
        if (sourceItems[iItem - 1].size > curBagSize) {// 当前物品大于包空间.肯定不能放入包中.
          okBags[iItem][curBagSize].Items.addAll(okBags[iItem - 1][curBagSize].Items);
        } else {
          int notIncludeValue = okBags[iItem - 1][curBagSize].getValue();// 不放当前物品包的价值
          int freeSize = curBagSize - sourceItems[iItem - 1].size;// 放当前物品包剩余空间
          int includeValue = sourceItems[iItem - 1].value + okBags[iItem - 1][freeSize].getValue();// 当前物品价值+放了当前物品后剩余包空间能放物品的价值
          if (notIncludeValue < includeValue) {// 放了价值更大就放入.
            okBags[iItem][curBagSize].Items.addAll(okBags[iItem - 1][freeSize].Items);
            okBags[iItem][curBagSize].Items.add(sourceItems[iItem - 1]);
          } else {// 否则不放入当前物品
            okBags[iItem][curBagSize].Items.addAll(okBags[iItem - 1][curBagSize].Items);
          }
        }

      }
    }
  }

  public static void main(String[] args) {
    Bag.doBag();
    for (int i = 0; i < Bag.itemCount + 1; i++) {// 打印所有方案中包含的物品
      for (int j = 0; j < Bag.bagSize + 1; j++) {
        System.out.print(Bag.okBags[i][j].Items);
      }
      System.out.println("");
    }

    for (int i = 0; i < Bag.itemCount + 1; i++) {// 打印所有方案中包的总价值
      for (int j = 0; j < Bag.bagSize + 1; j++) {
        System.out.print(Bag.okBags[i][j]);
      }
      System.out.println("");
    }

    OkBag okBagResult = Bag.okBags[Bag.itemCount][Bag.bagSize];
    System.out.println("最终结果为:" + okBagResult.Items.toString() + okBagResult);

  }

}

Das obige ist der detaillierte Inhalt vonBeispielanalyse zur Implementierung des Rucksackalgorithmus in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!