V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
nzynzynzy
V2EX  ›  程序员

今天碰到的一个看似简单的算法问题卡的我头疼:余额和构成余额的交易的问题,问 GPT 也没结果

  •  
  •   nzynzynzy · 34 天前 · 2659 次点击
    这是一个创建于 34 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我抽象一下这个问题:invoices 是销售行为,transaction 是对余额的操作行为,一通存取反复拉扯之后形成的余额,尝试去扣款,如果余额足够就允许交易,如果余额不足就拒绝交易。

    const invoices = [
      { id: 'INV001', type: 'Buy', amount: 100 }
    ];
    
    const balanceTransactions = [
      { id: 'JNL001', type: 'transaction', amount: 100 },
      { id: 'JNL002', type: 'transaction', amount: -100 },
      { id: 'JNL003', type: 'transaction', amount: 100 },
      { id: 'JNL004', type: 'transaction', amount: -100 },
      { id: 'JNL005', type: 'transaction', amount: 130}
    ];
    
    

    以上情况中,应该是 JNL001 到 JNL005 都被使用了,截至 JNL005 余额还剩 30 块,invoice 是 100 块。换句话说,就是尽可能多地查找余额的操作行为,确定哪些行为可以归结到这张 invoice 下。

    请问这叫什么算法,以下是 GPT 的结果肯定是不对的

    function performVerification() {
      const verifications = []; // 存储核销结果
    
      let remainingAmount = 0; // 剩余待核销金额
    
      // 按日期排序单据数组
      const sortedInvoices = invoices.sort((a, b) => a.date - b.date);
      const sortedJournals = journals.sort((a, b) => a.date - b.date);
    
      // 遍历单据数组进行核销
      for (const invoice of sortedInvoices) {
        let verifiedAmount = 0; // 当前单据已核销金额
        const verifiedJournals = []; // 当前单据核销的 journal 数组
    
        // 倒序遍历 journals 进行核销
        for (let i = sortedJournals.length - 1; i >= 0; i--) {
          const journal = sortedJournals[i];
    
          if (journal.amount < 0 && Math.abs(journal.amount) <= remainingAmount) {
            // 负数调整余额
            verifiedAmount += Math.abs(journal.amount);
            verifiedJournals.push({ id: journal.id, amount: Math.abs(journal.amount) });
            remainingAmount -= Math.abs(journal.amount);
            sortedJournals.splice(i, 1); // 从数组中移除已核销的 journal
          }
    
          // 如果当前单据已核销金额达到单据金额,则退出循环
          if (verifiedAmount >= invoice.amount) {
            break;
          }
        }
    
        // 添加核销结果到数组
        verifications.push({ invoice, verifiedAmount, verifiedJournals });
    
        // 如果已核销所有 journals ,则跳出循环
        if (sortedJournals.length === 0) {
          break;
        }
      }
    
      return verifications;
    }
    
    第 1 条附言  ·  33 天前
    实践下来 cumsum 比较接近但是需要找到所有大于 invoice 金额的情况,然后找到最后一个大于 invoice 的值,或者一组值中最靠前的一个,这个 index 之前的自数组算作这个 invoice 的核销范围。

    但是 cumsum 需要遍历所有数组,找到所有的符合条件的元素的 index ,不如变形为已知 total 倒推,这样遇到第一个就是要找的。

    非常抽象,让不少朋友疑惑了,不好意思!也很感谢几位朋友解读,帮助很大!
    第 2 条附言  ·  31 天前
    感谢大家回复,我把最终解法贴出来

    https://jsfiddle.net/4pyejfL8/
    34 条回复    2024-06-08 08:47:27 +08:00
    ivvei
        1
    ivvei  
       34 天前 via Android   ❤️ 1
    问题描述得乱七八槽。transaction 只能叫发生,不能叫使用。而且你这 JNL005 之后不是还有 130 吗,怎么就 100 了?要关联 invoice 为何不直接在 transaction 里面带上 invoice 的编号?正常人都这么做的啊。你根据金额倒推,遇到同样金额的 invoice 不是懵逼了?
    nzynzynzy
        2
    nzynzynzy  
    OP
       34 天前
    @ivvei #1 叫发生没什么问题。这个是我抽象的结果,就是打个比方。用户希望通过一笔消费能看到这笔能对应上几笔发生。

    这个 transaction 和 invoice 不是一一对应的,你可以想象为客户既可以消费也可以存取,存取并不是指定消费的。

    我疏漏了一些描述:
    - 就是一顿存取之后,只有一笔 invoice ,不会是多笔。
    - 没用到的单子就会自动结转等待下一次使用。

    这个数据,算法希望对应的结果应该是

    JNL001 ,金额 100 ,使用 100 ,余额 0
    JNL002 ,金额-100 ,使用-100 ,余额 0
    JNL003 ,金额 100 ,使用 100 ,余额 0
    JNL004 ,金额-100 ,使用-100 ,余额 0
    JNL005 ,金额 130 ,使用 100 ,余额 30
    zizon
        3
    zizon  
       34 天前
    看着像币圈侧链/次级账户交易合并回主链的操作...

    你合并 transaction 的时候检查更新余额看有没超不就行了?
    NoOneNoBody
        4
    NoOneNoBody  
       34 天前
    我理解就叫结算啊,或者集中结算
    JNL*是可实施或不实施?只是有序订单?赊账?

    你这问题问得不清楚,太难明了,不怪 GPT 答错
    RecursiveG
        5
    RecursiveG  
       34 天前
    建议楼主先去把自己的思路捋顺了再问。
    Chad0000
        6
    Chad0000  
       34 天前
    你把 transaction 理解为记账就理解了。transaction 加起来就是余额,余额你可以缓存/冗余起来。
    rekulas
        7
    rekulas  
       34 天前
    有点像数字货币的 utxo 的概念

    不过这个逻辑很简单,不清楚你有什么疑惑
    wingor2015
        8
    wingor2015  
       34 天前
    额, 看完之后感觉没完全看懂,建议楼主详细描述一下,比如举个例子账号从初始状态开始开始,然后每执行一次行为,invoices 和 transaction 各为什么状态,
    nzynzynzy
        9
    nzynzynzy  
    OP
       34 天前
    感谢各位耐心阅读。

    比如以下事件按顺序发生

    刚开始余额是 0
    ==============
    操作余额#JNL001 ,金额 100
    操作余额#JNL002 ,金额-100
    操作余额#JNL003 ,金额 100
    操作余额#JNL004 ,金额-100
    操作余额#JNL005 ,金额 130
    ===============
    截至目前账户余额是 130 元,此时发生了一单交易 INV001 ,价值 100 元
    这一单需说明“这 100 块是从哪些余额操作中来的”,这时候目前面临无数种算法列举 3 种可能性

    可能性 A:先进先出,够用就停
    INV001 的 100 元来自 JNL001

    可能性 B:先进先出,尽可能地记录
    INV001 的 100 元来自 JNL001-JNL005 的叠加
    JNL001 ,金额 100 ,核销 100 ,余额 0
    JNL002 ,金额-100 ,核销-100 ,余额 0
    JNL003 ,金额 100 ,核销 100 ,余额 0
    JNL004 ,金额-100 ,核销-100 ,余额 0
    JNL005 ,金额 130 ,核销 100 ,余额 30

    可能性 C:
    选一个够用的最大的,即 JNL005 去核销,其他无视

    这个例子中追求的算法是以上的 B ,即尽可能记录 INV001 的来源
    nzynzynzy
        10
    nzynzynzy  
    OP
       34 天前
    确实这个东西昨天让我有点心烦意乱的,我打了个草稿放在 V2 然后今天发了,可能真的懂得只有我。

    =============================
    然后还有一个规则就是“贪婪”先进先出地消耗 JNL ,耗完就停止,举个例子

    刚开始余额是 0
    ----
    操作余额#JNL001 ,金额 100
    操作余额#JNL002 ,金额-100
    操作余额#JNL003 ,金额 100
    操作余额#JNL004 ,金额-100
    操作余额#JNL005 ,金额 130
    销售 INV001 ,金额 100=>操作核销掉 JNL001-004 全部余额,因为他们叠加起来余额是 0 ,然后核销掉 JNL005 的 100 元,剩 30 元
    -----
    操作余额#JNL006 ,金额 100
    这时候发生交易 INV002 ,金额 130 ,此时需要记录 INV002 的来源:
    JNL005 ,金额 30 ,核销 30 ,余额 0 ,
    JNL006 ,金额 100 ,核销 100 ,余额 0

    情况大概就是这么个情况,看看还有什么没讲明白

    =============================

    @zizon #3
    @NoOneNoBody #4
    @RecursiveG #5
    @Chad0000 #6
    @rekulas #7
    @wingor2015 #8

    烦请各位如果有思路分享一下,有兴趣也可以插眼回来看
    Sawyerhou
        11
    Sawyerhou  
       34 天前 via Android
    我看了 15min 都没看明白,这是行情数据吗?

    inv 代表 K 线的成交额
    trans 代表每笔订单的成交额
    每根 K 线成交额由数量不确定的订单成交额加总得到

    现在想做数据对齐
    找出指定 K 线由哪些订单合成的?

    如果是想问以上的话
    这个对齐几乎不可能
    NessajCN
        12
    NessajCN  
       34 天前   ❤️ 1
    我也完全没看懂,你说的是中文吗
    JNL 是啥?为啥要纠结余额从哪里扣,
    是不是你有跟这个楼主 https://v2ex.com/t/1033839 类似的需求,也就是余额会过期?
    NoOneNoBody
        13
    NoOneNoBody  
       34 天前   ❤️ 1
    pandas 有个函数叫 cumsum ,就是对一个数列,每个元素,向首个元素方向所有包含的元素求和,得出一个新数列
    例如 1,2,3,4,5 结果为 1,3,6,10,15

    现有一个数 5 ,满足 x>=5 ,求 x 的位置
    对应 A ,从首位开始,6 为第一个满足的,位置为 3 ,有效的就是前三条
    对应 B ,从末尾开始,15 为第一个满足的,位置为 5 ,则全部有效
    C 就是 1,2,3,4,5 中选一个,与 cumsum 无关,位置为 5 ,有效的为仅第五条
    NoOneNoBody
        14
    NoOneNoBody  
       34 天前   ❤️ 2
    @all
    OP 实际需要求的是一个条件 mask ,覆盖若干条 JNL 构成 True
    如果上述 JNL 有序,可按#13 方案;如果无序,那就复杂了,需要排列组合
    Chad0000
        15
    Chad0000  
       34 天前 via iPhone   ❤️ 1
    @NessajCN
    op 应该在做 invoice 结算系统。invoice 提前发给客户,然后客户在某个时间早期转账支付了就行。那个 transaction 就是支付记录。国外很多系统都是这么运行。


    如果是这样,客户打款直接记录进账 transaction ,然后触发余额检查,如果够就产生一笔扣 invoice 的 transaction ,如果不够可以有多少扣多少。如果客户多转钱了,还是扣 invoice 那么多,但会导致所有 transaction 加起来为正数,也就是用户的账户处于 credit 状态(有余额)。

    不知我怎么说 op 明白了没有?还是你的系统不是这样的?
    @nzynzynzy
    @nzynzynzy
    @nzynzynzy
    nzynzynzy
        16
    nzynzynzy  
    OP
       34 天前
    @Chad0000 #15 原理有点类似,或者你可以理解为预存/预支 + 购买,而且这个购买的时候要找到对应的预存/预支记录,而且预存/预支是有可能像我描述的可能性 A 这样被第一个记录拦截住,而后面其实还有预支。理想情况是能读取到第五张单据

    @NoOneNoBody #13 谢谢,cumsum 确实是这个问题目前最贴切的描述,就是贪婪版的 cumsum ,我去朝着这个方向再探一探

    也欢迎其他朋友继续看看!
    nzynzynzy
        17
    nzynzynzy  
    OP
       34 天前
    @NessajCN #12 多谢这个还真的很类似!我感觉余额会过期是一种类似的情况,都是有序的先进先出地消耗,我继续去读一下
    NessajCN
        18
    NessajCN  
       34 天前 via Android
    @nzynzynzy 那你就也参考区块链只记录交易信息呗。
    nzynzynzy
        19
    nzynzynzy  
    OP
       34 天前
    @Chad0000 #15 而且你的例子中假设是 invoice 是可以 pending 状态先进来等待付款,和我的情况有差别,我的更像是进来时候实时判断钱够不够,不够这笔就废止了。我觉得老哥说的 cumsum 是有道理的,而且是正负都存在的 cumsum 。

    这个就变成了:cumsum 的数组中找值大于 invoice 的情况,其中最靠队尾的、值大于等于 invoice 的一个或者一群值中最靠前的一个。累死我了这个描述。。。
    ddzzhen
        20
    ddzzhen  
       34 天前 via Android
    既然有冲有送,应该把金额按来源分类打标签,金额与 transaction 独立,这样遇到 invoices 时候才容易明确来源和条件判断
    cybort
        21
    cybort  
       34 天前 via Android
    你需要给每一块钱加个编号,要不可能不唯一
    changyang
        22
    changyang  
       34 天前
    ```javascript
    //看了一下问题,不知道我理解对了没,以下是我的思路:
    //把 invoice 和 transaction 都当作一个交易表里面的记录,只是 type 不一样,就可以解决
    const transactions = [
    { id: 1, type: 'invoice', name: 'JNL001',amount:100,balance:100 },
    { id: 2, type: 'invoice', name: 'JNL002',amount:-100,balance:0 },
    { id: 3, type: 'invoice', name: 'JNL003',amount:100,balance:100 },
    { id: 4, type: 'invoice', name: 'JNL004',amount:-100,balance:0 },
    { id: 5, type: 'invoice', name: 'JNL005',amount:130,balance:130 },
    { id: 6, type: 'transaction', name: 'INV001',amount:-100,balance:30 },
    { id: 7, type: 'invoice', name: 'JNL006',amount:100,balance:130 },
    { id: 8, type: 'invoice', name: 'JNL007',amount:-100,balance:30 },
    { id: 9, type: 'transaction', name: 'INV002',amount:-100,balance:0 }
    ];

    function findRecordsBetween(name) {
    const index = transactions.findIndex(transaction => {
    if (transaction.name === name){
    if(transaction.type === 'transaction'){
    return true;
    }else {
    throw new Error('必须输入一个 transaction 的 name');
    }
    }
    });
    if (index === -1) {
    return []; // 如果未找到与该名称匹配的记录,返回空数组
    }
    const transactionIndex = transactions.slice(0, index ).findLastIndex(transaction => transaction.type === 'transaction');
    if (transactionIndex === -1) {
    return transactions.slice(0, index); // 如果未找到最近一次 transaction ,返回到开始所有记录
    }

    return transactions.slice(transactionIndex + 1, index);
    }

    // 用例:

    console.log(findRecordsBetween('INV001'));


    ```
    catamaran
        23
    catamaran  
       33 天前
    说半天都是数据,没看明白啥场景,可能是超出我的知识域了
    zizon
        24
    zizon  
       33 天前
    @nzynzynzy 感觉你的疑惑点可能在于有 n 个 transaction, m 个 invoice 要冲销, m>=2 的场景.
    在 multi invoice 的情况下,不通冲销策略造成的余额可能不一致(不确定)?

    其实可能是个背包问题?
    合并若干个可能是顺序的 transaction 使它满足>= 某个 invoice?
    Motorola3
        25
    Motorola3  
       33 天前
    @nzynzynzy 有一点不太理解 JNL01-04 都是 0 了 你为什么还要核销掉? 按照你这个逻辑 岂不是后续每次销售操作 都会核销掉前面所有的 余额为 0 的? 这不合理啊

    感觉可以将你的需求理解为 你的余额会过期 因为正常情况只有销售操作会减少余额吧 如果你 JNL002 减去 100 那么就说明他不是销售操作就类似于过期操作咯?

    假设你的 JNL005 是 100 元 JNL006 是 30 元

    然后你触发了 一个 120 元的销售操作 那么按理来说应该是取出所有的非 0 金额 计算总金额是否足够
    足够的话 按照时间由远到近排序 然后去扣除
    这样的话你每次扣除 都可以给这个 JNL 类加一个状态为 INV001 销售扣除 xxx 金额 这样就可以记录每笔操作以及操作的来源了
    xuanbg
        26
    xuanbg  
       33 天前
    看题目的意思是只要余额大于等于销售金额就可以交易,否则不能。这余额多少,不是 const balanceTransactions = [
    { id: 'JNL001', type: 'transaction', amount: 100 },
    { id: 'JNL002', type: 'transaction', amount: -100 },
    { id: 'JNL003', type: 'transaction', amount: 100 },
    { id: 'JNL004', type: 'transaction', amount: -100 },
    { id: 'JNL005', type: 'transaction', amount: 130}
    ];
    这个交易记录汇总出来的 130 么?需要对应具体哪一条交易记录么?没这个道理啊???
    nzynzynzy
        27
    nzynzynzy  
    OP
       33 天前
    @xuanbg 这个是关于账户的操作就比较敏感一点,用户看不见对应的、没办法核查就感到不放心。而且当时牛 p 吹出去了就做了吧虽然难度增加了。
    nzynzynzy
        28
    nzynzynzy  
    OP
       33 天前
    @Motorola3 是的。这是一个例子,实际上可能增增减减数额不会这样完全一致,可能是 100 ,-98 ,110 ,-9.98 这样。
    这个情境里不仅销售会减小余额,对余额直接操作也会。而目的是寻找销售对应的余额操作(可能增加、减少),减少余额的操作不用考虑找对应。
    nzynzynzy
        29
    nzynzynzy  
    OP
       33 天前
    @zizon 对的无论 m 还是 n 都是有序的。不同冲销策略确实会导致冲销单据的范围不一定,但是余额是一定的因为余额是 transaction 的累加,和进出无关。
    ZeroAsh
        30
    ZeroAsh  
       33 天前
    看下来感觉 transaction 应该也包括 invoice ,但毕竟 transaction 不是账户,只是一个流水出入记录,但是看你的描述 transaction 又有账户的概念,是不是账户的概念模型耦合到你的支出收入模型了,可以的话建议还是抽象出账户的模型,然后在结算 invoice 的时候,先求账户最新的 balance 数值是多少,然后复式记账记到对应的账上。

    不改模型的话,硬是拿 transaction 来推支出是被哪些收入的话是能推的,但前提是必须保证 transactions 是有序的。(其实远离也是建帐号的模型,每个收入都是一个帐号)


    算法可以参考下面的代码(文本编辑器写的可能有语法错误,看个大概思路吧)
    https://pastebin.mozilla.org/vUZwkyXf
    xhawk
        31
    xhawk  
       33 天前 via Android
    我是觉得你把事情复杂化了,应该有个 balance 表,然后每笔的 transactions 记录核销金额,核销发票的 id 就好了。没必要用啥算法。
    nzynzynzy
        32
    nzynzynzy  
    OP
       31 天前
    感谢大家回复,我把最终方案扔在 append 中了,欢迎批评

    冒昧艾特一下参与讨论的朋友,也算有个交代。谢谢大家!

    https://jsfiddle.net/4pyejfL8/

    @xhawk #31
    @ZeroAsh #30
    @xuanbg #26
    @catamaran #23
    @changyang #22
    @cybort #21
    @ddzzhen #20
    @Motorola3 #25
    @zizon #24
    @Chad0000 #15
    @NoOneNoBody #13
    @Sawyerhou #11
    @NessajCN #12
    @wingor2015 #8
    @rekulas #7
    @ivvei #1

    如有遗漏重复请海涵。祝各位今天有个好心情。
    nzynzynzy
        33
    nzynzynzy  
    OP
       31 天前
    另 1:我司部署的环境不支持 TS 因此用 js 写
    另 2:我一些代码是 gpt 写的以节约时间,所以代码风格不一致,见谅
    xhawk
        34
    xhawk  
       8 天前
    @nzynzynzy 挺好的, 看了一下代码, 思路是对的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2346 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 02:20 · PVG 10:20 · LAX 19:20 · JFK 22:20
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.