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

[nzynzynzy]

我抽象一下这个问题：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;
}

实践下来 cumsum 比较接近但是需要找到所有大于 invoice 金额的情况，然后找到最后一个大于 invoice 的值，或者一组值中最靠前的一个，这个 index 之前的自数组算作这个 invoice 的核销范围。

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

非常抽象，让不少朋友疑惑了，不好意思！也很感谢几位朋友解读，帮助很大！

感谢大家回复，我把最终解法贴出来

https://jsfiddle.net/4pyejfL8/

[ivvei]

问题描述得乱七八槽。transaction 只能叫发生，不能叫使用。而且你这 JNL005 之后不是还有 130 吗，怎么就 100 了？要关联 invoice 为何不直接在 transaction 里面带上 invoice 的编号？正常人都这么做的啊。你根据金额倒推，遇到同样金额的 invoice 不是懵逼了？

[nzynzynzy]

@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]

看着像币圈侧链/次级账户交易合并回主链的操作...

你合并 transaction 的时候检查更新余额看有没超不就行了?

[NoOneNoBody]

我理解就叫结算啊，或者集中结算
JNL*是可实施或不实施？只是有序订单？赊账？

你这问题问得不清楚，太难明了，不怪 GPT 答错

[RecursiveG]

建议楼主先去把自己的思路捋顺了再问。

[Chad0000]

你把 transaction 理解为记账就理解了。transaction 加起来就是余额，余额你可以缓存/冗余起来。

[rekulas]

有点像数字货币的 utxo 的概念

不过这个逻辑很简单,不清楚你有什么疑惑

[wingor2015]

额， 看完之后感觉没完全看懂，建议楼主详细描述一下，比如举个例子账号从初始状态开始开始，然后每执行一次行为，invoices 和 transaction 各为什么状态，

[nzynzynzy]

感谢各位耐心阅读。

比如以下事件按顺序发生

刚开始余额是 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]

确实这个东西昨天让我有点心烦意乱的，我打了个草稿放在 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]

我看了 15min 都没看明白，这是行情数据吗？

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

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

如果是想问以上的话
这个对齐几乎不可能

[NessajCN]

我也完全没看懂，你说的是中文吗
JNL 是啥？为啥要纠结余额从哪里扣，
是不是你有跟这个楼主 https://v2ex.com/t/1033839 类似的需求，也就是余额会过期？

[NoOneNoBody]

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]

@all
OP 实际需要求的是一个条件 mask ，覆盖若干条 JNL 构成 True
如果上述 JNL 有序，可按#13 方案；如果无序，那就复杂了，需要排列组合

[Chad0000]

@NessajCN
op 应该在做 invoice 结算系统。invoice 提前发给客户，然后客户在某个时间早期转账支付了就行。那个 transaction 就是支付记录。国外很多系统都是这么运行。


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

不知我怎么说 op 明白了没有？还是你的系统不是这样的？
@nzynzynzy
@nzynzynzy
@nzynzynzy

[nzynzynzy]

@Chad0000 #15 原理有点类似，或者你可以理解为预存/预支 + 购买，而且这个购买的时候要找到对应的预存/预支记录，而且预存/预支是有可能像我描述的可能性 A 这样被第一个记录拦截住，而后面其实还有预支。理想情况是能读取到第五张单据

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

也欢迎其他朋友继续看看！

[nzynzynzy]

@NessajCN #12 多谢这个还真的很类似！我感觉余额会过期是一种类似的情况，都是有序的先进先出地消耗，我继续去读一下

[NessajCN]

@nzynzynzy 那你就也参考区块链只记录交易信息呗。

[nzynzynzy]

@Chad0000 #15 而且你的例子中假设是 invoice 是可以 pending 状态先进来等待付款，和我的情况有差别，我的更像是进来时候实时判断钱够不够，不够这笔就废止了。我觉得老哥说的 cumsum 是有道理的，而且是正负都存在的 cumsum 。

这个就变成了：cumsum 的数组中找值大于 invoice 的情况，其中最靠队尾的、值大于等于 invoice 的一个或者一群值中最靠前的一个。累死我了这个描述。。。

[ddzzhen]

既然有冲有送，应该把金额按来源分类打标签，金额与 transaction 独立，这样遇到 invoices 时候才容易明确来源和条件判断

[cybort]

你需要给每一块钱加个编号，要不可能不唯一

[changyang]

```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]

说半天都是数据，没看明白啥场景，可能是超出我的知识域了

[zizon]

@nzynzynzy 感觉你的疑惑点可能在于有 n 个 transaction, m 个 invoice 要冲销, m>=2 的场景.
在 multi invoice 的情况下,不通冲销策略造成的余额可能不一致(不确定)?

其实可能是个背包问题?
合并若干个可能是顺序的 transaction 使它满足>= 某个 invoice?

[ZnductR0MjHvjRQ3]

@nzynzynzy 有一点不太理解 JNL01-04 都是 0 了 你为什么还要核销掉？ 按照你这个逻辑 岂不是后续每次销售操作 都会核销掉前面所有的 余额为 0 的？ 这不合理啊

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

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

然后你触发了 一个 120 元的销售操作 那么按理来说应该是取出所有的非 0 金额 计算总金额是否足够
足够的话 按照时间由远到近排序 然后去扣除
这样的话你每次扣除 都可以给这个 JNL 类加一个状态为 INV001 销售扣除 xxx 金额 这样就可以记录每笔操作以及操作的来源了

[xuanbg]

看题目的意思是只要余额大于等于销售金额就可以交易，否则不能。这余额多少，不是 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]

@xuanbg 这个是关于账户的操作就比较敏感一点，用户看不见对应的、没办法核查就感到不放心。而且当时牛 p 吹出去了就做了吧虽然难度增加了。

[nzynzynzy]

@Motorola3 是的。这是一个例子，实际上可能增增减减数额不会这样完全一致，可能是 100 ，-98 ，110 ，-9.98 这样。
这个情境里不仅销售会减小余额，对余额直接操作也会。而目的是寻找销售对应的余额操作（可能增加、减少），减少余额的操作不用考虑找对应。

[nzynzynzy]

@zizon 对的无论 m 还是 n 都是有序的。不同冲销策略确实会导致冲销单据的范围不一定，但是余额是一定的因为余额是 transaction 的累加，和进出无关。

[ZeroAsh]

看下来感觉 transaction 应该也包括 invoice ，但毕竟 transaction 不是账户，只是一个流水出入记录，但是看你的描述 transaction 又有账户的概念，是不是账户的概念模型耦合到你的支出收入模型了，可以的话建议还是抽象出账户的模型，然后在结算 invoice 的时候，先求账户最新的 balance 数值是多少，然后复式记账记到对应的账上。

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


算法可以参考下面的代码（文本编辑器写的可能有语法错误，看个大概思路吧）
https://pastebin.mozilla.org/vUZwkyXf

[xhawk]

我是觉得你把事情复杂化了，应该有个 balance 表，然后每笔的 transactions 记录核销金额，核销发票的 id 就好了。没必要用啥算法。

[nzynzynzy]

感谢大家回复，我把最终方案扔在 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]

另 1：我司部署的环境不支持 TS 因此用 js 写
另 2：我一些代码是 gpt 写的以节约时间，所以代码风格不一致，见谅

[xhawk]

@nzynzynzy 挺好的， 看了一下代码， 思路是对的。