今天碰到的一个看似简单的算法问题卡的我头疼:余额和构成余额的交易的问题,问 GPT 也没结果
我抽象一下这个问题: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 倒推,这样遇到第一个就是要找的。非常抽象,让不少朋友疑惑了,不好意思!也很感谢几位朋友解读,帮助很大!
问题描述得乱七八槽。transaction 只能叫发生,不能叫使用。而且你这 JNL005 之后不是还有 130 吗,怎么就 100 了?要关联 invoice 为何不直接在 transaction 里面带上 invoice 的编号?正常人都这么做的啊。你根据金额倒推,遇到同样金额的 invoice 不是懵逼了?
#1 叫发生没什么问题。这个是我抽象的结果,就是打个比方。用户希望通过一笔消费能看到这笔能对应上几笔发生。这个 transaction 和 invoice 不是一一对应的,你可以想象为客户既可以消费也可以存取,存取并不是指定消费的。我疏漏了一些描述:- 就是一顿存取之后,只有一笔 invoice ,不会是多笔。- 没用到的单子就会自动结转等待下一次使用。这个数据,算法希望对应的结果应该是JNL001 ,金额 100 ,使用 100 ,余额 0JNL002 ,金额-100 ,使用-100 ,余额 0JNL003 ,金额 100 ,使用 100 ,余额 0JNL004 ,金额-100 ,使用-100 ,余额 0JNL005 ,金额 130 ,使用 100 ,余额 30
看着像币圈侧链/次级账户交易合并回主链的操作...你合并 transaction 的时候检查更新余额看有没超不就行了?
我理解就叫结算啊,或者集中结算JNL*是可实施或不实施?只是有序订单?赊账?你这问题问得不清楚,太难明了,不怪 GPT 答错
建议楼主先去把自己的思路捋顺了再问。
你把 transaction 理解为记账就理解了。transaction 加起来就是余额,余额你可以缓存/冗余起来。
有点像数字货币的 utxo 的概念不过这个逻辑很简单,不清楚你有什么疑惑
额, 看完之后感觉没完全看懂,建议楼主详细描述一下,比如举个例子账号从初始状态开始开始,然后每执行一次行为,invoices 和 transaction 各为什么状态,
感谢各位耐心阅读。比如以下事件按顺序发生刚开始余额是 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 ,余额 0JNL002 ,金额-100 ,核销-100 ,余额 0JNL003 ,金额 100 ,核销 100 ,余额 0JNL004 ,金额-100 ,核销-100 ,余额 0JNL005 ,金额 130 ,核销 100 ,余额 30可能性 C:选一个够用的最大的,即 JNL005 去核销,其他无视这个例子中追求的算法是以上的 B ,即尽可能记录 INV001 的来源
确实这个东西昨天让我有点心烦意乱的,我打了个草稿放在 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情况大概就是这么个情况,看看还有什么没讲明白============================= #3 #4 #5 #6 #7 #8 烦请各位如果有思路分享一下,有兴趣也可以插眼回来看
我看了 15min 都没看明白,这是行情数据吗?inv 代表 K 线的成交额trans 代表每笔订单的成交额每根 K 线成交额由数量不确定的订单成交额加总得到现在想做数据对齐找出指定 K 线由哪些订单合成的?如果是想问以上的话这个对齐几乎不可能
我也完全没看懂,你说的是中文吗JNL 是啥?为啥要纠结余额从哪里扣,是不是你有跟这个楼主 hesudu.com/t/1033839 类似的需求,也就是余额会过期?
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 ,有效的为仅第五条
OP 实际需要求的是一个条件 mask ,覆盖若干条 JNL 构成 True如果上述 JNL 有序,可按#13 方案;如果无序,那就复杂了,需要排列组合
op 应该在做 invoice 结算系统。invoice 提前发给客户,然后客户在某个时间早期转账支付了就行。那个 transaction 就是支付记录。国外很多系统都是这么运行。如果是这样,客户打款直接记录进账 transaction ,然后触发余额检查,如果够就产生一笔扣 invoice 的 transaction ,如果不够可以有多少扣多少。如果客户多转钱了,还是扣 invoice 那么多,但会导致所有 transaction 加起来为正数,也就是用户的账户处于 credit 状态(有余额)。不知我怎么说 op 明白了没有?还是你的系统不是这样的?
#15 原理有点类似,或者你可以理解为预存/预支 + 购买,而且这个购买的时候要找到对应的预存/预支记录,而且预存/预支是有可能像我描述的可能性 A 这样被第一个记录拦截住,而后面其实还有预支。理想情况是能读取到第五张单据 #13 谢谢,cumsum 确实是这个问题目前最贴切的描述,就是贪婪版的 cumsum ,我去朝着这个方向再探一探也欢迎其他朋友继续看看!
#12 多谢这个还真的很类似!我感觉余额会过期是一种类似的情况,都是有序的先进先出地消耗,我继续去读一下
那你就也参考区块链只记录交易信息呗。
#15 而且你的例子中假设是 invoice 是可以 pending 状态先进来等待付款,和我的情况有差别,我的更像是进来时候实时判断钱够不够,不够这笔就废止了。我觉得老哥说的 cumsum 是有道理的,而且是正负都存在的 cumsum 。这个就变成了:cumsum 的数组中找值大于 invoice 的情况,其中最靠队尾的、值大于等于 invoice 的一个或者一群值中最靠前的一个。累死我了这个描述。。。
既然有冲有送,应该把金额按来源分类打标签,金额与 transaction 独立,这样遇到 invoices 时候才容易明确来源和条件判断
你需要给每一块钱加个编号,要不可能不唯一
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'));
说半天都是数据,没看明白啥场景,可能是超出我的知识域了
感觉你的疑惑点可能在于有 n 个 transaction, m 个 invoice 要冲销, m>=2 的场景.在 multi invoice 的情况下,不通冲销策略造成的余额可能不一致(不确定)?其实可能是个背包问题?合并若干个可能是顺序的 transaction 使它满足>= 某个 invoice?
有一点不太理解 JNL01-04 都是 0 了 你为什么还要核销掉? 按照你这个逻辑 岂不是后续每次销售操作 都会核销掉前面所有的 余额为 0 的? 这不合理啊感觉可以将你的需求理解为 你的余额会过期 因为正常情况只有销售操作会减少余额吧 如果你 JNL002 减去 100 那么就说明他不是销售操作就类似于过期操作咯?假设你的 JNL005 是 100 元 JNL006 是 30 元 然后你触发了 一个 120 元的销售操作 那么按理来说应该是取出所有的非 0 金额 计算总金额是否足够足够的话 按照时间由远到近排序 然后去扣除这样的话你每次扣除 都可以给这个 JNL 类加一个状态为 INV001 销售扣除 xxx 金额 这样就可以记录每笔操作以及操作的来源了
看题目的意思是只要余额大于等于销售金额就可以交易,否则不能。这余额多少,不是 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 么?需要对应具体哪一条交易记录么?没这个道理啊???
这个是关于账户的操作就比较敏感一点,用户看不见对应的、没办法核查就感到不放心。而且当时牛 p 吹出去了就做了吧虽然难度增加了。
是的。这是一个例子,实际上可能增增减减数额不会这样完全一致,可能是 100 ,-98 ,110 ,-9.98 这样。这个情境里不仅销售会减小余额,对余额直接操作也会。而目的是寻找销售对应的余额操作(可能增加、减少),减少余额的操作不用考虑找对应。
对的无论 m 还是 n 都是有序的。不同冲销策略确实会导致冲销单据的范围不一定,但是余额是一定的因为余额是 transaction 的累加,和进出无关。
看下来感觉 transaction 应该也包括 invoice ,但毕竟 transaction 不是账户,只是一个流水出入记录,但是看你的描述 transaction 又有账户的概念,是不是账户的概念模型耦合到你的支出收入模型了,可以的话建议还是抽象出账户的模型,然后在结算 invoice 的时候,先求账户最新的 balance 数值是多少,然后复式记账记到对应的账上。不改模型的话,硬是拿 transaction 来推支出是被哪些收入的话是能推的,但前提是必须保证 transactions 是有序的。(其实远离也是建帐号的模型,每个收入都是一个帐号)算法可以参考下面的代码(文本编辑器写的可能有语法错误,看个大概思路吧) pastebin.mozilla.org/vUZwkyXf
我是觉得你把事情复杂化了,应该有个 balance 表,然后每笔的 transactions 记录核销金额,核销发票的 id 就好了。没必要用啥算法。
今天在微博上看到了 有人分享了下面的这段函数式代码,我把代码贴到下面,不过我对原来的代码略有改动,对于函数式的版本,咋一看,的确令人非常费解,仔细看一下,你可能就晕掉了,似乎完…
刚从 iPhone 切过来,用的三星,24h 爬梯子,发现这手机白天在使用 app (非游戏)的时候耗电和息屏待机的耗电速度几乎差不多。也就是说白天我息屏待机 1 小时和我亮屏…
目前我的主力桌面端开发框架用 javafx ,简单点的用 electron ,但是各自有各自的缺点。 我司开发的主要是工业软件,涉及到串口通信等硬件交互,IO 密集、计算密集。…