利用多重背包解决噩梦循环（花最少的金币买灵魂凑够100临界值）

欧皇小涛12138 · 2025-12-8 11:30 发表于山东

本帖最后由欧皇小涛12138 于 2025-12-8 14:55 编辑

利用多重背包解决噩梦循环（花最少的金币买灵魂凑够100临界值）1

上周写一门课的课程报告，正好遇到dnf噩梦循环的例子，就以这个为例子写了报告。用了多重背包的思想（0-1背包，一个物品选或者不选；分数背包，一个物品可以拆成分数选择；完全背包，一个物品可以选择的次数无上限；多重背包，一个物品可以选择多次，但选择次数有上限）
老师课上讲的是0-1背包和部分背包，都不适用于这个例子，所以我就问AI，了解另外2种背包，发现多重背包非常适合该问题。
采用了2种解法，分别是暴力枚举和动态规划，上周四交报告的时候比较敷衍，最后给出的解不实用（因为我报告里是从临界值和价值入手，性价比=价值/临界值=10，这里的价值就简单写成了深渊票的个数，由于性价比一样，所有最终所有凑够100临界值的结果都是“最优解”），并未解决真正的问题：如何选择灵魂使得花费最少？
现在想起来还是有点遗憾的，但文章已经上交也没法改了，还是有点可惜的。
本着务实的态度，就上了游戏，看了拍卖行里5个灵魂结晶的平均价格，把相关数据写进代码里，利用上述算法就出来了最优解。
因为噩梦循环一次最少投入5个稀有/神器灵魂，这里稀有和神器填的是5个对应灵魂的价格。
这里灵魂的来源为全部从拍卖行金币获取，也就是说，如果你所有灵魂都是拍卖行买的情况下，这是最优解。
实际上目前游戏里传说灵魂确实是“最没用的”，稀有+神器换虚无，史诗调试，太初各种罐子。
具体代码如下，python代码，AI写的，我自己看代码发现没有明显的错误（也可能我学艺不精看不出来错误

）

代码1暴力枚举

# 定义各灵魂的属性：临界值(vi)、价值(pi)、数量上限(max_count)
soul_attrs = {
"稀有": {"vi": 1, "pi": 7768*5, "max": 20},
"神器": {"vi": 2, "pi": 44433*5, "max": 10},
"传说": {"vi": 3, "pi": 109472, "max": 33},
"史诗": {"vi": 9, "pi": 717012, "max": 11},
"太初": {"vi": 100, "pi": 5555525, "max": 1}
}
min_value = float('inf')  # 初始化最小价值为无穷大
valid_combinations = []  # 存储所有合法组合及其价值
# -------------------- 第一层循环：太初的数量（n5，最多1个） --------------------
for n5 in range(soul_attrs["太初"]["max"] + 1):
remaining = 100 - n5 * soul_attrs["太初"]["vi"]
if remaining < 0:  # 太初数量过多，临界值超过100，跳过
continue
# -------------------- 第二层循环：史诗的数量（n4，最多11个） --------------------
max_n4 = min(soul_attrs["史诗"]["max"], remaining // soul_attrs["史诗"]["vi"])
for n4 in range(max_n4 + 1):
      remaining_n4 = remaining - n4 * soul_attrs["史诗"]["vi"]
      if remaining_n4 < 0:  # 史诗数量过多，临界值不足，跳过
continue
      # -------------------- 第三层循环：传说的数量（n3，最多33个） --------------------
max_n3 = min(soul_attrs["传说"]["max"], remaining_n4 // soul_attrs["传说"]["vi"])
      for n3 in range(max_n3 + 1):
         remaining_n3 = remaining_n4 - n3 * soul_attrs["传说"]["vi"]
         if remaining_n3 < 0:  # 传说数量过多，临界值不足，跳过
continue
         # -------------------- 第四层循环：神器的数量（n2，最多10个） --------------------
max_n2 = min(soul_attrs["神器"]["max"], remaining_n3 // soul_attrs["神器"]["vi"])
         for n2 in range(max_n2 + 1):
            remaining_n2 = remaining_n3 - n2 * soul_attrs["神器"]["vi"]
            if remaining_n2 < 0:  # 神器数量过多，临界值不足，跳过
continue
            # -------------------- 第五层：稀有的数量（n1，由剩余临界值确定） --------------------
n1 = remaining_n2
            if n1 < 0 or n1 > soul_attrs["稀有"]["max"]:  # 稀有数量超上限，跳过
continue
            # ---------- 计算当前组合的总价值，并记录合法组合 ----------
total_value = (
                     n1 * soul_attrs["稀有"]["pi"] +
                     n2 * soul_attrs["神器"]["pi"] +
                     n3 * soul_attrs["传说"]["pi"] +
                     n4 * soul_attrs["史诗"]["pi"] +
                     n5 * soul_attrs["太初"]["pi"]
            )
            valid_combinations.append(((n1, n2, n3, n4, n5), total_value))
            # 更新最小价值
if total_value < min_value:
                  min_value = total_value
# -------------------- 输出所有合法组合及最小价值 --------------------
print("===== 所有满足条件的组合（临界值和为100） =====")
for i, (combo, value) in enumerate(valid_combinations, 1):
n1, n2, n3, n4, n5 = combo
print(f"组合{i}: 稀有{n1}个，神器{n2}个，传说{n3}个，史诗{n4}个，太初{n5}个 → 总价值{value}")
print(f"\n===== 最小价值为：{min_value} =====")

代码2动态规划

# 首先定义灵魂属性
soul_attrs = {
"稀有": {"vi": 1, "pi": 7768*5, "max": 20},
"神器": {"vi": 2, "pi": 44433*5, "max": 10},
"传说": {"vi": 3, "pi": 109472, "max": 33},
"史诗": {"vi": 9, "pi": 717012, "max": 11},
"太初": {"vi": 100, "pi": 5555525, "max": 1}
}
def multiple_knapsack_dp(soul_attrs, capacity=100):
"""
多重背包问题动态规划解法
返回达到临界值100的所有可能组合及其价值 """
# 初始化DP数组，dp[j]表示达到临界值j时的最小价值
dp = [float('inf')] * (capacity + 1)
dp[0] = 0  # 临界值为0时，价值为0
# 记录路径，用于回溯具体方案
path = [[] for _ in range(capacity + 1)]
path[0] = [(0, 0, 0, 0, 0)]  # 初始状态：(稀有,神器,传说,史诗,太初)
# 按特定顺序处理灵魂类型
soul_order = ["稀有", "神器", "传说", "史诗", "太初"]
for soul_name in soul_order:
      attr = soul_attrs[soul_name]
      vi, pi, max_count = attr["vi"], attr["pi"], attr["max"]
      # 二进制优化：将数量上限拆分为2的幂次组合
k = 1
      remaining = max_count
      while remaining > 0:
         count = min(k, remaining)
         weight = count * vi
         value = count * pi
         # 逆序遍历容量（类似0-1背包）
for j in range(capacity, weight - 1, -1):
            if dp[j - weight] + value < dp[j]:
                  dp[j] = dp[j - weight] + value
                  # 更新路径
path[j] = []
                  for prev_comb in path[j - weight]:
                     new_comb = list(prev_comb)
                     # 根据灵魂类型更新数量
soul_index = soul_order.index(soul_name)
                     new_comb[soul_index] += count
                     path[j].append(tuple(new_comb))
         remaining -= count
         k *= 2
return dp[capacity], path[capacity]
# 使用动态规划求解
min_value, combinations = multiple_knapsack_dp(soul_attrs)
print("===== 动态规划解法 =====")
print(f"达到临界值100的最小价值为：{min_value}")
print("\n所有最优组合：")
for i, combo in enumerate(combinations, 1):
n1, n2, n3, n4, n5 = combo
print(f"组合{i}: 稀有{n1}个，神器{n2}个，传说{n3}个，史诗{n4}个，太初{n5}个")

最后结果

蛮力枚举结果：
共计有736种组合可以达到100点临界值的约束条件。
利用多重背包解决噩梦循环（花最少的金币买灵魂凑够100临界值）2

在结果里利用ctrl+f查找最小价值的数即为最优解对应的灵魂组合：
利用多重背包解决噩梦循环（花最少的金币买灵魂凑够100临界值）3

利用动态规划验证，结果一致：
利用多重背包解决噩梦循环（花最少的金币买灵魂凑够100临界值）4

所以上述问题的最优解就是33个传说灵魂+5个稀有灵魂（我这里代码里稀有和神器是一组，对应游戏内的5个，因为噩梦循环最少一次性投入5个灵魂）凑够100临界值。
不同跨区的玩家可以自己电脑下载一个pycharm，复制动态规划代码（这个算的时间复杂度低），修改各灵魂的价格，即可获得最优解（我想应该差距不大）。