P1049 [NOIP 2001 普及组] 装箱问题(语言-ruby)

Question

这段代码函数无限调用自身，会导致栈溢出（Stack Overflow），这就叫递归：函数内部调用自身。
但是，如果你往函数里加入一个参数，并当参数超限时自动return;，就可以避免这种情况！
我们定义递归函数void f(i,j)表示正在处理第i个物品，其最大占用空间为j。
在每个函数里都有两个决策：要和不要

Answer 1

让 “紫雾凌寒” 来帮你回答,本回答结合 DeepSeek

如果还有问题，请评论或点击头像私信，如果有帮助到您, 请关注、采纳、点赞

1. 关键点分析：
   - 原始代码存在函数无限递归调用导致栈溢出的问题。
   - 解决思路是通过增加一个参数来控制递归边界，当参数达到某个限制时停止递归。
2. 解决方案：
   - 以下是一个用Ruby解决装箱问题的代码示例，通过增加参数来避免无限递归：

def packing(volume, items, index, used_volume)
  if index == items.size
    return used_volume
  end
  # 不放入当前物品
  skip_result = packing(volume, items, index + 1, used_volume)
  # 尝试放入当前物品
  if used_volume + items[index] <= volume
    put_result = packing(volume, items, index + 1, used_volume + items[index])
    return [skip_result, put_result].max
  end
  return skip_result
end

volume = 200
items = [3, 5, 8, 10, 15, 18, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100]
result = packing(volume, items, 0, 0)
puts result

• 在这个代码中，packing函数有四个参数：
  • volume：表示箱子的总体积。
  • items：是一个数组，包含各个物品的体积。
  • index：当前考虑的物品索引。
  • used_volume：当前已经使用的体积。
• 当index等于物品数组的大小items.size时，表示所有物品都已考虑，返回当前使用的体积used_volume。
• 每次递归时，先计算不放入当前物品的结果skip_result，然后判断放入当前物品是否可行（即used_volume + items[index] <= volume），如果可行则计算放入当前物品后的结果put_result，最后返回两者中的最大值。
  3. 多种解决方案的优缺点：
• 递归方案：
  • 优点：代码逻辑清晰，符合问题的递归性质，易于理解。
  • 缺点：如题目中提到的，容易出现栈溢出问题，对于大规模数据时性能较差。
• 动态规划方案：
  • 优点：避免了递归带来的栈溢出问题，性能较好，适用于大规模数据。
  • 缺点：代码相对复杂，需要更多的空间来存储中间结果。
• 动态规划的Ruby代码示例如下：

volume = 200
items = [3, 5, 8, 10, 15, 18, 20, 25, 3, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100]
dp = Array.new(volume + 1, 0)

items.each do |item|
  (item..volume).each do |v|
    dp[v] = [dp[v], dp[v - item] + item].max
  end
end

puts dp[volume]

• 在这个动态规划代码中，dp数组用于存储每个体积下能装入的最大物品体积和。通过遍历物品数组，逐步更新dp数组，最终dp[volume]即为能装入箱子的最大物品体积和。
  4. 总结：

• 对于装箱问题，递归方法虽然直观但有栈溢出风险，动态规划是更优的选择，它在避免栈溢出的同时能高效处理大规模数据。在实际应用中，应根据具体情况选择合适的算法。如果数据规模较小且对代码简洁性要求较高，递归方法可以作为初步尝试；但对于大规模数据，动态规划能提供更好的性能。

• 上述代码示例中的动态规划方案可以有效解决装箱问题，并且能避免递归带来的栈溢出问题，在处理此类问题时是一种较为可靠的方法。

希望以上解答对您有所帮助。如果您有任何疑问，欢迎在评论区提出。