今天碰到的一个看似简单的算法问题卡的我头疼：余额和构成余额的交易的问题，问 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;
}

changyang

41 天前

```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'));

```

Motorola3

40 天前

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

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

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

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

ZeroAsh

40 天前

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

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

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