java - 我正在尝试使用 Java 和递归解决 "knapsack"问题

Question

这是一个学校作业，教授规定必须使用递归，并且必须在 GUI 框中单行输入，其中第一个数字是背包可以容纳的最大容量(重量)，其余是元素重量。这不包括值(value)，只包括重量。

它部分工作，因为它正确地跟随树并指示有多少解决方案(通过调试输出)，但我无法记录有效的解决方案。由于存储和删除 sack[] 数组中的项目，在分支末尾时，递归调用的返回似乎工作正常。

据我单步执行代码一百万次可以看出，当返回其他地方时它会失败。这使得袋子里留下了不应该存在的杂物。希望有人能够看到我在哪里做了愚蠢的事情并帮助我朝正确的方向前进。我已经多次删除并重写了其中的代码，以至于我几乎要把我的计算机扔出窗外。哈哈

我知道这很多，但除了发布整个程序之外，我想不出如何正确描述我遇到的问题。预先感谢任何人能够提供的任何帮助。

import javax.swing.*;
import java.util.Arrays;

// Main Program
class n00868494 {

   static int itemCount = 0; // total number of items 
   static int pos = 0; // position indicator in the "sack" array
   static int sack[] = new int[25]; // sack to hold items on right branches

   public static void main(String[] args) {

   String sinput[] = new String[25]; // temp string array to hold parameters before     converting to integers
   int items[] = new int[25]; // array to hold the items
   int capacity = 0; // knapsack capacity
   String s = null; // temp string to hold user input

   while (true) { // infinite loop

      // Use a JOptionPane dialog to get the user's input
      s = JOptionPane.showInputDialog(new JFrame("Input Params"), "Please enter total weight, followed a list of item weights)","Run Parameters",JOptionPane.QUESTION_MESSAGE);

      if ((s == null) || (s.equals(""))) { // user pressed X, cancel or left it blank.
         System.exit(0);  // exit cleanly
      }

      sinput = s.split(" "); // split the parameters on the whitespace

      for (int i = 0; i < sinput.length; i++) { // iterate through the array and copy the elements to the correct variables
         if (i == 0) {
            capacity = Integer.parseInt(sinput[i], 10); // knapsack weight in the first position
         } else {
            items[i-1] = Integer.parseInt(sinput[i], 10); // the rest are item weights
         }
      }
     items = Arrays.copyOfRange(items, 0, sinput.length - 1); // truncate the items array to remove empty elements at the end

      knapSack(capacity, items); // call the knapsack method that will in turn call the recursive function
   }   
      }

   public static void knapSack(int capacity, int[] items) {

      itemCount = items.length; // keep track of original number of items

      recknapSack(capacity, items, 0); // start recursive calls
   }


   /*
      recursive knapsack method: called repeatedly to find the correct combinations of items such that their weights
  total to the max capacity that the knapsack can hold

      capacity: knapsack capacity
      items: array of items (weights)
      branch: flag indicating whether the call is a left branch (item not included) or right branch (item included)
         0 - initial call, non recursive
         1 - left branch, weight not included
         2 - right branch, weight included
   */
   public static void recknapSack(int capacity, int[] items, int branch) {

      System.out.print("\nCap: " + capacity + " Items: " + Arrays.toString(items)); // recursive call tracking debugging

      if (capacity == 0){ // debugging - for breaking at certain points in the tree
         assert Boolean.TRUE; // set breakpoint on this line
      }


      // base cases - ends of the branches
      if (capacity == 0){ // sack is exactly full, item weights = total weight
            System.out.print("\t  -> good tree"); // debugging
            //JOptionPane.showMessageDialog(new JFrame("Results"), "The valid combinations are: ");
            Arrays.fill(sack, 0); // clear the sack, this was a successful branch, will start again for another solution
            return;
      } else if (capacity < 0) { // bag overloaded
            System.out.print("\t  -> overload tree"); // debugging
            if (branch == 2) // if this is an "included" branch
               sack[--pos] = 0; // remove the last item placed in the sack
        return;
           } else if (items.length == 0){ // out of items and/or capacity not reached
        System.out.print("\t  -> empty src tree"); // debugging
        if (branch == 2)
           sack[--pos] = 0;
        return;
   } else {

     int firstItem; // this the first item, it will either be discarded (not included) or placed in the sack array (included)
     firstItem = items[0];

     items = Arrays.copyOfRange(items, 1, items.length); // for either recursive branch: remove the first item from the list

     recknapSack(capacity, items, 1); // call recursive function, left branch, where item is discarded and not placed in sack

     // prepare for right branch, where item is placed in sack
     capacity -= firstItem; // subtract the left most item weight from from capacity
     sack[pos++] = firstItem; // place the item in the sack
     recknapSack(capacity, items, 2); // recursive right branch call, item is placed in sack, weight subtracted from capacity

  }

  return;
   }
}

Answer 1

您的代码中发生的情况是，当它到达最后一个 else 语句时，它并没有删除放入的初始值。我对您的代码做了一个小更改，这可能会给您带来您正在寻找的结果。首先，我让递归函数返回一个 int，这将是容量:

 public static int recknapSack(int capacity, int[] items, int branch) {

我将每个返回语句更改为:

 return capacity;

然后在 else 语句中，我添加了以下内容:

 else {

             int firstItem; // this the first item, it will either be discarded (not included) or placed in the sack array (included)
             firstItem = items[0];

             items = Arrays.copyOfRange(items, 1, items.length); // for either recursive branch: remove the first item from the list

             recknapSack(capacity, items, 1); // call recursive function, left branch, where item is discarded and not placed in sack

             // prepare for right branch, where item is placed in sack
             capacity -= firstItem; // subtract the left most item weight from from capacity
             int temp = pos;
             sack[pos++] = firstItem; // place the item in the sack
             System.out.println("First item " + firstItem);
             int ret = recknapSack(capacity, items, 2); // recursive right branch call, item is placed in sack, weight subtracted from capacity
             if(ret != 0)
             {
                  System.out.println("Removing " + sack[temp] + " at position " + (temp));
                 sack[temp] = 0;
                 pos = temp;
             }


      }

除非容量不为 0，否则这将使麻袋保持不变。如果您发现麻袋为 0，您仍然会从麻袋中删除所有内容，因此如果您需要存储该信息，我建议在以下情况下它确实有效，您将麻袋存储到数组的 ArrayList 中，其中将包含所有完美的解决方案。如果您在没有完美解决方案的情况下需要解决方案，您也可以将每个解决方案存储在那里，并按容量最低的顺序排列。

希望有帮助。