618购物的凑单问题与财务凑数问题

可以叫我才哥

发布于 2024-04-26 15:00:59

830

发布于 2024-04-26 15:00:59

unsetunset凑单问题unsetunset

对于各类凑单问题，最经典的就是淘宝双十一的满减促销活动，比如“满 200 元减 50 元”。假设你的购物车中有 n 个（n>100）想买的商品，希望从里面选几个，在凑够满减条件的前提下，让选出来的商品价格总和最大程度地接近满减条件（200 元），如何编程解决这个问题？

动态规划解决

使用传统的编程思路就是使用动态规划，思路如下：

购物车中有 n 个商品，针对每个商品都决策是否购买。每次决策之后，对应不同的状态集合。用一个二维数组 s t a t e s [ n ] [ x ] states[n][x] states[n][x]，来记录每次决策之后所有可达的状态。

python实现代码为：

def double11advance(items_info: list, w: int):
    """
    动态规划解决双11凑单问题
    :param items_info: 每个商品价格
    :param w: 满减条件，比如 200
    :return:
    """
    n = len(items_info)
    # 超过 3 倍就没有薅羊毛的价值了
    states = [[False] * (3 * w + 1) for i in range(n)]
    states[0][0] = True
    states[0][items_info[0]] = True
    for i in range(1, n):
        for j in range(3 * w + 1):
            if states[i - 1][j]:
                # 不购买第i个商品
                states[i][j] = states[i - 1][j]
                # 购买第i个商品
                nw = j + items_info[i]
                if nw <= 3 * w:
                    states[i][nw] = True
    j = w
    while j < 3 * w + 1 and not states[n - 1][j]:
        j += 1
    # j是大于等于 w 的最小值
    if j == 3 * w + 1:
        return  # 没有可行解
    idx = []
    for i in range(n - 1, 0, -1):
        if j - items_info[i] >= 0 and states[i - 1][j - items_info[i]]:
            idx.append(i)
            j -= items_info[i]
    if j != 0:
        idx.append(0)
    return sorted(idx)

假设，我们的购物车中每件商品的价格为：

48, 30, 19, 36, 36, 27, 42, 42, 36, 24,  40, 70, 32

我们执行代码：

import numpy as np
items_info = np.array([48, 30, 19, 36, 36, 27, 42, 42, 36, 24,  40, 70, 32])

idx = double11advance(items_info, 200)
print("选中商品的索引：", idx)
print("选中商品的价格：", items_info[idx])
print("总价格：", sum(items_info[idx]))

选中商品的索引： [1, 4, 7, 8, 9, 12]
选中商品的价格： [30 36 42 36 24 32]
总价格： 200

可以看到程序完美的找到了一组可行解。

除了动态规划，我们还可以使用回溯算法解决，参考代码就不公布了，接下来我们直接使用优化算法解决这个问题。

优化算法解决

在前面的文章《OR-Tools官档中文用法大全（CP、LP、VRP、Flows等）》中的背包与装箱问题一章中，我演示了使用SCIP求解器解决该问题。

不过SCIP求解器速度较慢，而且想获取多个可行解实现起来较为麻烦，所以这里我演示使用ortools的cp_model求解器来解决该问题。

cp_model求解器相对于前面的SCIP求解器的缺点在于只能处理整数。

代码如下：

from ortools.sat.python import cp_model
import numpy as np

model = cp_model.CpModel()
items_info = np.array([48, 30, 19, 36, 36, 27, 42, 42, 36, 24,  40, 70, 32])
items = np.arange(items_info.shape[0])
x = [model.NewBoolVar(f'x_{i}') for i in range(len(items_info))]
obj = (x*items_info).sum()
model.Add(obj >=200)
model.Minimize(obj)
solver = cp_model.CpSolver()
status = solver.Solve(model)
result = [bool(solver.Value(i)) for i in x]
print("选中商品的索引：", items[result])
print("选中商品的价格：", items_info[result])
print("总价格：", items_info[result].sum())

选中商品的索引： [ 1  4  7  8  9 12]
选中商品的价格： [30 36 42 36 24 32]
总价格： 200

可以看到 ortools 库得到了与前面动态规划一致的结果。

ortools获取多个可行解

下面我们考虑使用cp_model求解器获取多个可行解，前面我们已经可行解的最小值为200，下面我们可以限制总价格等于200：

from ortools.sat.python import cp_model
import numpy as np


class MyCpSolver(cp_model.CpSolverSolutionCallback):
    def __init__(self, x):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.x = x
        self.num = 0

    def on_solution_callback(self):
        self.num += 1
        print(f"第{self.num}个解")
        result = [bool(self.Value(i)) for i in self.x]
        print("选中商品的索引：", items[result])
        print("选中商品的价格：", items_info[result])
        print("总价格：", items_info[result].sum())


model = cp_model.CpModel()
items_info = np.array([48, 30, 19, 36, 36, 27, 42, 42, 36, 24,  40, 70, 32])
items = np.arange(items_info.shape[0])
x = [model.NewBoolVar(f'x_{i}') for i in range(len(items_info))]
obj = (x*items_info).sum()
model.Add(obj == 200)
solver = cp_model.CpSolver()
myCpSolver = MyCpSolver(x)
solver.parameters.enumerate_all_solutions = True
status = solver.Solve(model, myCpSolver)
print(solver.StatusName(status))
print("解的个数：", myCpSolver.num)

最终得到了30个可行解：

image-20221225161243648

如此多的可行解是因为36出现了三次，导致可行解的个数也被翻了3倍，实际可行解就只有10个。下面我们改进一下上面代码，让其获取唯一的可行解：

from collections import Counter
from ortools.sat.python import cp_model
import numpy as np


class MyCpSolver(cp_model.CpSolverSolutionCallback):
    def __init__(self, x):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.x = x
        self.num = 0

    def on_solution_callback(self):
        self.num += 1
        print(f"第{self.num}个解")
        idx = []
        result = []
        for i, xi in enumerate(self.x):
            v = self.Value(xi)
            if v == 0:
                continue
            idx.append(i)
            result.extend([items_info[i]]*v)
        print("选中商品的索引：", idx)
        print("选中商品的价格：", result)
        print("总价格：", sum(result))


arr = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24,  40, 70, 32]

model = cp_model.CpModel()
items_info = []
x = []
for i, (k, v) in enumerate(Counter(arr).items(), 1):
    items_info.append(k)
    x.append(model.NewIntVar(0, v, f"x{i}"))
items_info = np.array(items_info)
obj = (items_info*x).sum()
model.Add(obj == 200)
solver = cp_model.CpSolver()
myCpSolver = MyCpSolver(x)
solver.parameters.enumerate_all_solutions = True
status = solver.Solve(model, myCpSolver)
print(solver.StatusName(status))
print("解的个数：", myCpSolver.num)

第1个解
选中商品的索引： [1, 2, 4, 5, 7]
选中商品的价格： [30, 19, 27, 42, 42, 40]
总价格： 200
第2个解
选中商品的索引： [2, 3, 4, 5, 7]
选中商品的价格： [19, 36, 36, 27, 42, 40]
总价格： 200
第3个解
选中商品的索引： [2, 4, 5, 8]
选中商品的价格： [19, 27, 42, 42, 70]
总价格： 200
第4个解
选中商品的索引： [0, 2, 3, 4, 8]
选中商品的价格： [48, 19, 36, 27, 70]
总价格： 200
第5个解
选中商品的索引： [0, 2, 4, 5, 6, 7]
选中商品的价格： [48, 19, 27, 42, 24, 40]
总价格： 200
第6个解
选中商品的索引： [0, 1, 2, 3, 4, 7]
选中商品的价格： [48, 30, 19, 36, 27, 40]
总价格： 200
第7个解
选中商品的索引： [0, 5, 7, 8]
选中商品的价格： [48, 42, 40, 70]
总价格： 200
第8个解
选中商品的索引： [1, 3, 6, 7, 8]
选中商品的价格： [30, 36, 24, 40, 70]
总价格： 200
第9个解
选中商品的索引： [1, 3, 5, 6, 9]
选中商品的价格： [30, 36, 36, 42, 24, 32]
总价格： 200
第10个解
选中商品的索引： [0, 3, 5, 9]
选中商品的价格： [48, 36, 42, 42, 32]
总价格： 200
OPTIMAL
解的个数： 10

可以看到顺利的获取到唯一解。

unsetunset财务凑数问题unsetunset

财务凑数问题与前面的问题模型一致，区别在于存在小数，例如从一大批金额中找出能够合并出指定金额的组合。

假设我们要查找的金额列表如下：

7750.0, 50000.0, 94693.0, 89159.18, 59000.0, 19634.94, 27000.0, 37770.17, 55631.64, 23800.0,
20000.0, 20000.0, 20000.0, 72985.45, 48000.0, 48000.0, 58750.0, 22000.0, 11219.61, 45600.0,
90500.0, 84288.0, 930.0, 1352.0, 120.0, 750.0, 22880.0, 45678.0, 49555.0, 17181.54, 1925.0,
1500.0, 83325.0, 500.0, 1298.5, 36936.34, 91933.67, 5205.0, 20195.0, 20550.0, 10600.0, 3200.0,
6400.0, 6900.0, 9900.0, 9750.0, 9600.0, 7200.0, 15208.41, 10550.0, 21077.02, 75437.51, 73515.11,
3140.0, 85128.6, 87095.74, 22806.24, 961.72, 13285.47, 28980.0, 67997.62, 35955.33, 12890.27, 15459.47,
20124.58, 25246.66, 13216.11, 89400.0, 89400.0, 26800.0, 11365.0, 16457.0, 50000.0, 54309.0, 12000.0,
39000.0, 70569.5, 45231.5, 56400.0, 86400.0, 86400.0, 86400.0, 86400.0, 12000.0, 390.0, 2500.0, 38109.79,
5968.63, 14862.6, 45038.91, 63189.17, 80784.86, 37664.87, 4981.44, 50000.0, 50000.0, 32323.01, 567.73, 66056.88, 26400.0

我们需要找到95984的组合。

SCIP求解器直接计算

如果使用SCIP求解器可以直接计算结果，编码如下：

from ortools.linear_solver import pywraplp
import numpy as np

arr = [7750.0, 50000.0, 94693.0, 89159.18, 59000.0, 19634.94, 27000.0, 37770.17, 55631.64, 23800.0,
       20000.0, 20000.0, 20000.0, 72985.45, 48000.0, 48000.0, 58750.0, 22000.0, 11219.61, 45600.0,
       90500.0, 84288.0, 930.0, 1352.0, 120.0, 750.0, 22880.0, 45678.0, 49555.0, 17181.54, 1925.0,
       1500.0, 83325.0, 500.0, 1298.5, 36936.34, 91933.67, 5205.0, 20195.0, 20550.0, 10600.0, 3200.0,
       6400.0, 6900.0, 9900.0, 9750.0, 9600.0, 7200.0, 15208.41, 10550.0, 21077.02, 75437.51, 73515.11,
       3140.0, 85128.6, 87095.74, 22806.24, 961.72, 13285.47, 28980.0, 67997.62, 35955.33, 12890.27, 15459.47,
       20124.58, 25246.66, 13216.11, 89400.0, 89400.0, 26800.0, 11365.0, 16457.0, 50000.0, 54309.0, 12000.0,
       39000.0, 70569.5, 45231.5, 56400.0, 86400.0, 86400.0, 86400.0, 86400.0, 12000.0, 390.0, 2500.0, 38109.79,
       5968.63, 14862.6, 45038.91, 63189.17, 80784.86, 37664.87, 4981.44, 50000.0, 50000.0, 32323.01, 567.73, 66056.88, 26400.0]

items_info = np.array(arr)
items = np.arange(items_info.shape[0])
solver = pywraplp.Solver.CreateSolver('SCIP')
x = [solver.BoolVar(f'x_{i}') for i in range(len(items_info))]
obj = (x*items_info).sum()
solver.Add(obj >= 95984)
solver.Minimize(obj)
status = solver.Solve()
print("总重量：", obj.solution_value())
result = np.frompyfunc(lambda x: x.solution_value(), 1, 1)(x).astype(bool)
print("选中商品的索引：", items[result])
print("选中商品的价值：", items_info[result])
print("总价值：", items_info[result].sum())

总重量： 95984.3
选中商品的索引： [22 24 33 34 38 40 41 44 58 61]
选中商品的价值： [  930.     120.     500.    1298.5  20195.   10600.    3200.    9900.
 13285.47 35955.33]
总价值： 95984.3

不过这并不是真正的最优解，如果我们把约束设置为必须为目标值：

solver = pywraplp.Solver.CreateSolver('SCIP')
x = [solver.BoolVar(f'x_{i}') for i in range(len(items_info))]
obj = (x*items_info).sum()
solver.Add(obj == 95984)
status = solver.Solve()
print("总重量：", obj.solution_value())
result = np.frompyfunc(lambda x: x.solution_value(), 1, 1)(x).astype(bool)
print("选中商品的索引：", items[result])
print("选中商品的价值：", items_info[result])
print("总价值：", items_info[result].sum())

总重量： 95984.0
选中商品的索引： [ 5 18 25 30 38 39 43 45 53 57 84 97]
选中商品的价值： [19634.94 11219.61   750.    1925.   20195.   20550.    6900.    9750.
  3140.     961.72   390.     567.73]
总价值： 95984.0

可惜耗时接近10秒。

cp_model求解器

cp_model求解器只能处理整数，为了能够处理小数，我们可以将其乘以100后转换为整数：

from ortools.sat.python import cp_model
import numpy as np

arr = [7750.0, 50000.0, 94693.0, 89159.18, 59000.0, 19634.94, 27000.0, 37770.17, 55631.64, 23800.0,
       20000.0, 20000.0, 20000.0, 72985.45, 48000.0, 48000.0, 58750.0, 22000.0, 11219.61, 45600.0,
       90500.0, 84288.0, 930.0, 1352.0, 120.0, 750.0, 22880.0, 45678.0, 49555.0, 17181.54, 1925.0,
       1500.0, 83325.0, 500.0, 1298.5, 36936.34, 91933.67, 5205.0, 20195.0, 20550.0, 10600.0, 3200.0,
       6400.0, 6900.0, 9900.0, 9750.0, 9600.0, 7200.0, 15208.41, 10550.0, 21077.02, 75437.51, 73515.11,
       3140.0, 85128.6, 87095.74, 22806.24, 961.72, 13285.47, 28980.0, 67997.62, 35955.33, 12890.27, 15459.47,
       20124.58, 25246.66, 13216.11, 89400.0, 89400.0, 26800.0, 11365.0, 16457.0, 50000.0, 54309.0, 12000.0,
       39000.0, 70569.5, 45231.5, 56400.0, 86400.0, 86400.0, 86400.0, 86400.0, 12000.0, 390.0, 2500.0, 38109.79,
       5968.63, 14862.6, 45038.91, 63189.17, 80784.86, 37664.87, 4981.44, 50000.0, 50000.0, 32323.01, 567.73, 66056.88, 26400.0]
model = cp_model.CpModel()
items_info = (np.array(arr)*100).astype(int)
items = np.arange(items_info.shape[0])
x = [model.NewBoolVar(f'x_{i}') for i in range(len(items_info))]
obj = (x*items_info).sum()
model.Add(obj == 95984*100)
solver = cp_model.CpSolver()
status = solver.Solve(model)
print(solver.StatusName(status))
result = [bool(solver.Value(i)) for i in x]
print("选中商品的索引：", items[result])
print("选中商品的价格：", items_info[result]/100)
print("总价格：", items_info[result].sum()/100)

OPTIMAL
选中商品的索引： [ 0 23 24 41 42 47 53 70 71 75]
选中商品的价格： [ 7750.  1352.   120.  3200.  6400.  7200.  3140. 11365. 16457. 39000.]
总价格： 95984.0

获取多个可行解

可以看到财务的金额数据存在大量重复，所以必须先进行计数处理，最终代码为：

from collections import Counter
from ortools.sat.python import cp_model
import numpy as np


class MyCpSolver(cp_model.CpSolverSolutionCallback):
    def __init__(self, x):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.x = x
        self.num = 0

    def on_solution_callback(self):
        self.num += 1
        print(f"第{self.num}个解")
        idx = []
        result = []
        for i, xi in enumerate(self.x):
            v = self.Value(xi)
            if v == 0:
                continue
            idx.append(i)
            result.extend([items_info[i]/100]*v)
        print("选中商品的索引：", idx)
        print("选中商品的价格：", result)
        print("总价格：", sum(result))


arr = [7750.0, 50000.0, 94693.0, 89159.18, 59000.0, 19634.94, 27000.0, 37770.17, 55631.64, 23800.0,
       20000.0, 20000.0, 20000.0, 72985.45, 48000.0, 48000.0, 58750.0, 22000.0, 11219.61, 45600.0,
       90500.0, 84288.0, 930.0, 1352.0, 120.0, 750.0, 22880.0, 45678.0, 49555.0, 17181.54, 1925.0,
       1500.0, 83325.0, 500.0, 1298.5, 36936.34, 91933.67, 5205.0, 20195.0, 20550.0, 10600.0, 3200.0,
       6400.0, 6900.0, 9900.0, 9750.0, 9600.0, 7200.0, 15208.41, 10550.0, 21077.02, 75437.51, 73515.11,
       3140.0, 85128.6, 87095.74, 22806.24, 961.72, 13285.47, 28980.0, 67997.62, 35955.33, 12890.27, 15459.47,
       20124.58, 25246.66, 13216.11, 89400.0, 89400.0, 26800.0, 11365.0, 16457.0, 50000.0, 54309.0, 12000.0,
       39000.0, 70569.5, 45231.5, 56400.0, 86400.0, 86400.0, 86400.0, 86400.0, 12000.0, 390.0, 2500.0, 38109.79,
       5968.63, 14862.6, 45038.91, 63189.17, 80784.86, 37664.87, 4981.44, 50000.0, 50000.0, 32323.01, 567.73, 66056.88, 26400.0]

model = cp_model.CpModel()
items_info = []
x = []
for i, (k, v) in enumerate(Counter(arr).items(), 1):
    items_info.append(k)
    x.append(model.NewIntVar(0, v, f"x{i}"))
items_info = (np.array(items_info)*100).astype(int)
obj = (items_info*x).sum()
model.Add(obj == 95984*100)
solver = cp_model.CpSolver()
myCpSolver = MyCpSolver(x)
solver.parameters.enumerate_all_solutions = True
status = solver.Solve(model, myCpSolver)
print(solver.StatusName(status))
print("解的个数：", myCpSolver.num)

最终再经过一小时的等待后，并未找出全部的可行解，程序还在运行中，1小时找到一千多个可行解：

为了避免计算时间过长，我们可以设置最大执行时间，例如设置30秒：

solver.parameters.max_time_in_seconds = 30

可以看到30秒内能够找到45个解：

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2024-04-22，如有侵权请联系 cloudcommunity@tencent.com 删除

self

本文分享自可以叫我才哥微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度