我正在尝试使用 Java 和递归来解决 "knapsack" 问题
I'm trying to solve the "knapsack" problem using Java and recursion
这是学校作业，教授规定必须用递归，必须在gui框中单行输入，第一个数字是背包能装的最大容量（重量），其余的是物品重量。这不包括价值，只包括重量。
它部分工作，因为它正确地跟随树并指示有多少解决方案（通过调试输出），但我无法记录有效的解决方案。由于在 sack[] 数组中存储和删除项目，在分支的末端进行递归调用时，它似乎在 returns 上工作正常。
据我通过单步执行代码一百万次可以看出，它在返回其他地方时失败了。这会使袋子里留下不应该放在那里的杂物。希望有人能够看到我在哪里做一些愚蠢的事情并帮助我朝着正确的方向前进。我已经删除并重写了很多次其中的代码，以至于我要把我的电脑扔出 window。哈哈
我知道这很多，但除了发布整个程序之外，我想不出如何正确描述我遇到的问题。提前感谢任何人可能提供的任何帮助。
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;
}
}
你的代码中发生的事情是，当它到达最后一个 else 语句时，它并没有删除输入的初始值。我对你的代码做了一个小改动，可能会得到你想要的结果寻找。首先，我有一个递归函数 return 一个 int，它的容量是：
public static int recknapSack(int capacity, int[] items, int branch) {
我将每个 return 语句更改为：
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 中，该数组将包含所有完美的解决方案。如果你在没有完美方案的情况下需要方案，你也可以把每一个方案都存进去，按容量从小排序。
希望对您有所帮助。
这是学校作业，教授规定必须用递归，必须在gui框中单行输入，第一个数字是背包能装的最大容量（重量），其余的是物品重量。这不包括价值，只包括重量。
它部分工作，因为它正确地跟随树并指示有多少解决方案（通过调试输出），但我无法记录有效的解决方案。由于在 sack[] 数组中存储和删除项目，在分支的末端进行递归调用时，它似乎在 returns 上工作正常。
据我通过单步执行代码一百万次可以看出，它在返回其他地方时失败了。这会使袋子里留下不应该放在那里的杂物。希望有人能够看到我在哪里做一些愚蠢的事情并帮助我朝着正确的方向前进。我已经删除并重写了很多次其中的代码，以至于我要把我的电脑扔出 window。哈哈
我知道这很多，但除了发布整个程序之外，我想不出如何正确描述我遇到的问题。提前感谢任何人可能提供的任何帮助。
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;
}
}
你的代码中发生的事情是，当它到达最后一个 else 语句时，它并没有删除输入的初始值。我对你的代码做了一个小改动，可能会得到你想要的结果寻找。首先，我有一个递归函数 return 一个 int，它的容量是：
public static int recknapSack(int capacity, int[] items, int branch) {
我将每个 return 语句更改为：
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 中，该数组将包含所有完美的解决方案。如果你在没有完美方案的情况下需要方案，你也可以把每一个方案都存进去，按容量从小排序。
希望对您有所帮助。