-1

对于学校，我应该使用递归回溯来解决船难题。用户输入船的最大重量、物品类型的数量以及每种物品类型的重量和价值。每种物品类型中都可以放置一个以上的物品。

我们的任务是“程序应该找到一个解决方案，用选定的有价值的物品装满船，使船上物品的总价值最大化，而物品的总重量保持在船的承重范围内。”

它还具有用于递归回溯算法的非常具体的模板。

目前我正在使用连续的项目列表来存储可能的项目和船上的项目。item 结构包括重量、值、计数（使用次数）的 int 成员和用于打印目的的唯一代码。然后我有一个 Boat 类，其中包含数据成员 max_weight、current_weight、value_sum 和每个连续列表的成员，然后是解决难题所需的成员函数。我的所有类函数似乎都运行良好，并且在给定示例输入的情况下，我的递归确实显示了正确的答案。

我想不通的是额外得分的条件，即“修改你的程序，使其显示总权重最低的最佳解决方案。如果有两个总权重相同的解决方案，打破通过选择其中项目最少的解决方案来打成平手。” 我已经看了一段时间，但我只是不确定如何更改它以确保重量最小化同时也最大化价值。这是我的解决方案的代码：

bool solve(Boat &boat) {
    if (boat.no_more()) {
        boat.print();
        return true;
    }
    else {
        int pos;
        for (int i = 0; i < boat.size(); i++){
            if (boat.can_place(i)) {
                pos = boat.add_item(i);
                bool solved = solve(boat);
                boat.remove_item(pos);
                if (solved) return true;
            }

        }
        return false;
    }
}

所有函数的功能几乎完全符合其名称。如果船上没有任何可能的物品，则不再返回 true。Size 返回可能项目列表的大小。添加和删​​除项目会相应地更改项目计数数据以及 Boat current_weight 和 value_sum 成员。此外，add_item、remove_item 和 can_place 参数是正在使用的可能项目的索引。为了确保找到最大值，可能项目的列表在 Boat 的构造函数中按值降序排序，该构造函数将可能项目列表作为参数。

这里还有一个输入和输出的例子： 输入输出示例

非常感谢任何见解！

4

1 回答 1

1

事实证明，上述解决方案是正确的。我得到错误答案的唯一原因是我实现了 nomore() 函数。在函数中，我正在检查可能项目列表中的任何项目是否小于船上剩余的重量。我应该检查它们是否小于或等于船上的重量。一个简单的错误。

维基百科条目确实有用，我喜欢漫画:)

于 2014-06-24T23:02:11.300 回答