求一个优惠券最大叠加

Question

业务需要商品立即购买时自动选择叠加的优惠卷，然后将id数组发给后端计算价格

有很多金额相同和不相同的优惠卷，不用考虑满减，要求
1.将商品价格抵扣到0或最接近0优先
2.券用的越多越好，也就是优先使用小额度的券

如果商品68元 有 1张50 2张30 6张10 4张2 此时用 6张10 + 4张2

Answer 1

这样应该可以了，就只测试了一个题目给的68块的数据。

interface Coupon {
    /**
     * 优惠券ID
     */
    id: number
    /**
     * 优惠券面额
     */
    price: number
}

/**
 * 原地排序，面额最低优先
 * @param coupon 优惠券数组
 */
function sort(coupon: Coupon[]) {
    coupon.sort((a, b) => a.price - b.price)
}

/**
 * 得到尽可能抵扣到总价格的优惠券使用方案，尽可能多使用小面额优惠券
 * @param allPrice 总价格
 * @param coupon 可以使用的优惠券（多张）
 * @returns 建议的优惠券使用方案
 */
function getCouponPlan(allPrice: number, coupon: Coupon[]): Coupon[] {
    const array = [...coupon] // 复制
    sort(array) // 排序

    let price = 0 // 已折扣价格
    const usedCoupon: Coupon[] = [] // 已使用的优惠券

    while (price <= allPrice) {
        const foundCoupon = array.shift()
        if (foundCoupon) {
            if (price + foundCoupon.price > allPrice) {
                // 若这张优惠券抵扣了,折扣价格就会超过总价了，就不用这张优惠券
                break
            }
            price += foundCoupon.price
            usedCoupon.push(foundCoupon)
        } else {
            // 优惠券用完了
            break
        }
    }

    return usedCoupon
}

const myCoupon: Coupon[] = []
myCoupon.push({ id: 1, price: 50 })

myCoupon.push({ id: 2, price: 30 })
myCoupon.push({ id: 3, price: 30 })

myCoupon.push({ id: 4, price: 10 })
myCoupon.push({ id: 5, price: 10 })
myCoupon.push({ id: 6, price: 10 })
myCoupon.push({ id: 7, price: 10 })
myCoupon.push({ id: 8, price: 10 })
myCoupon.push({ id: 9, price: 10 })

myCoupon.push({ id: 10, price: 2 })
myCoupon.push({ id: 11, price: 2 })
myCoupon.push({ id: 12, price: 2 })
myCoupon.push({ id: 13, price: 2 })


const usedCoupon = getCouponPlan(68, myCoupon)

let usedPrice = 0
usedCoupon.forEach(c => usedPrice += c.price)

console.log(`使用了${usedCoupon.length}张优惠券，一共抵扣了${usedPrice}块钱`)
console.log('[68块钱] 优惠券使用方案', usedCoupon)

改了一个版本哈哈哈

新版本

interface Coupon {
    /**
     * 优惠券ID
     */
    id: number
    /**
     * 优惠券面额
     */
    price: number
}

/**
 * 原地排序，面额最低优先
 * @param coupon 优惠券数组
 */
function sort(coupon: Coupon[]) {
    coupon.sort((a, b) => a.price - b.price)
}

/**
 * 原地排序，面额最高优先
 * @param coupon 优惠券数组
 */
function sortByBigerFirst(coupon: Coupon[]) {
    coupon.sort((a, b) => b.price - a.price)
}


/**
 * 得到尽可能抵扣到总价格的优惠券使用方案，尽可能多使用小面额优惠券
 * @param allPrice 总价格
 * @param coupon 可以使用的优惠券（多张）
 * @returns 建议的优惠券使用方案
 */
function getCouponCountUsedMaxPlan(allPrice: number, coupon: Coupon[]): Coupon[] {
    const array = [...coupon] // 复制
    sort(array) // 排序

    let price = 0 // 已折扣价格
    const usedCoupon: Coupon[] = [] // 已使用的优惠券

    while (price <= allPrice) {
        const foundCoupon = array.shift()
        if (foundCoupon) {
            if (price + foundCoupon.price > allPrice) {
                // 若这张优惠券抵扣了,折扣价格就会超过总价了，则仅使用这张优惠券后结束叠加计算
                // 即允许再使用一张优惠券 将商品价格抵扣到0（折扣价格可以溢出超过总价）
                price += foundCoupon.price
                usedCoupon.push(foundCoupon)
                break
            }
            price += foundCoupon.price
            usedCoupon.push(foundCoupon)
        } else {
            // 优惠券用完了
            break
        }
        if (price === allPrice) {
            // 刚好这一轮，完美抵扣，则不再计算抵扣
            break
        }
    }

    return usedCoupon
}

const myCoupon: Coupon[] = []
myCoupon.push({ id: 1, price: 50 })

myCoupon.push({ id: 2, price: 30 })
myCoupon.push({ id: 3, price: 30 })

myCoupon.push({ id: 4, price: 10 })
myCoupon.push({ id: 5, price: 10 })
myCoupon.push({ id: 6, price: 10 })
myCoupon.push({ id: 7, price: 10 })
myCoupon.push({ id: 8, price: 10 })
myCoupon.push({ id: 9, price: 10 })

myCoupon.push({ id: 10, price: 2 })
myCoupon.push({ id: 11, price: 2 })
myCoupon.push({ id: 12, price: 2 })
myCoupon.push({ id: 13, price: 2 })


const couponAllPrice = myCoupon.map(m => m.price).reduce((last, cur) => last += cur)

console.log('[优惠券最大抵扣金额]', couponAllPrice)

function testCouponCountUsedMaxPlan(myCount: number) {
    const usedCoupon = getCouponCountUsedMaxPlan(myCount, myCoupon)

    let usedPrice = 0
    usedCoupon.forEach(c => usedPrice += c.price)
    console.log(`[总价：${myCount}块钱] 使用了${usedCoupon.length}张优惠券，一共抵扣了${usedPrice}块钱`)
    console.log(`[总价：${myCount}块钱] 优惠券张数最大化使用方案`, usedCoupon)
}

function test(myCount: number) {
    testCouponCountUsedMaxPlan(myCount)
}

test(68)
test(66)
test(70)
test(43)
test(5)
test(29)
test(102)
test(147)
test(198)
test(241)

再改一个版本，优先用面额大的优惠券

interface Coupon {
    /**
     * 优惠券ID
     */
    id: number
    /**
     * 优惠券面额
     */
    price: number
}


/**
 * 有条件地删除部分优惠券，就地删除
 * @param couponList 优惠券列表
 * @param needDelete 判断是否需要删除某个优惠券的回调函数
 * @returns 被删除的优惠券集合
 */
function deleteSomeCoupon(couponList: Coupon[], needDelete: (c: Coupon) => boolean): Coupon[] {
    let testCoupon = couponList[0]
    const deleted: Coupon[] = []

    while (testCoupon = couponList.shift()) {
        if (!needDelete(testCoupon)) {
            couponList.unshift(testCoupon)
            break
        }
        deleted.push(testCoupon)
    }
    return deleted
}


/**
 * 原地排序，面额最低优先
 * @param coupon 优惠券数组
 */
function sortValueMinFirst(coupon: Coupon[]) {
    coupon.sort((a, b) => a.price - b.price)
}

/**
 * 原地排序，面额最高优先
 * @param coupon 优惠券数组
 */
function sortValueMaxFirst(coupon: Coupon[]) {
    coupon.sort((a, b) => b.price - a.price)
}

/**
 * 得到尽可能抵扣到总价格的优惠券使用方案，使得折扣后的价格接近于0，尽可能多使用大面额优惠券
 * @param allPrice 总价格
 * @param coupon 可以使用的优惠券（多张）
 * @returns 建议的优惠券使用方案
 */
function getCouponPlanByLimitDiscountPriceToZero(allPrice: number, coupon: Coupon[]) {
    const couponList = [...coupon]
    // 面额越大的优惠券排在越前面
    sortValueMaxFirst(couponList)

    let price = 0 // 折扣价格
    const usedCoupon: Coupon[] = []

    while (price <= allPrice) {
        const foundCoupon = couponList.shift()
        if (foundCoupon) {
            // 找到了优惠券
            if (price + foundCoupon.price > allPrice) {
                // 当前面额的优惠券折扣后会超过总价，应当跳过不适用此种面额的优惠券

                // 当前这个过大面额的优惠券放回，在下一行统一删除
                couponList.unshift(foundCoupon)
                // 删除剩余的，与当前面额相同的所有优惠券
                deleteSomeCoupon(couponList, (c) => c.price === foundCoupon.price)

                continue
            }

            // 计算折扣
            usedCoupon.push(foundCoupon)
            price += foundCoupon.price

            if (price === allPrice) {
                // 当前优惠券折扣后会等于总价，不再计算折扣
                break
            }
        } else {
            // 优惠券用完了
            break
        }
    }

    return usedCoupon
}

const myCoupon: Coupon[] = []

myCoupon.push({ id: 1, price: 50 })

myCoupon.push({ id: 2, price: 30 })
myCoupon.push({ id: 3, price: 30 })

myCoupon.push({ id: 4, price: 10 })
myCoupon.push({ id: 5, price: 10 })
myCoupon.push({ id: 6, price: 10 })
myCoupon.push({ id: 7, price: 10 })
myCoupon.push({ id: 8, price: 10 })
myCoupon.push({ id: 9, price: 10 })

myCoupon.push({ id: 10, price: 2 })
myCoupon.push({ id: 11, price: 2 })
myCoupon.push({ id: 12, price: 2 })
myCoupon.push({ id: 13, price: 2 })

const couponAllPrice = myCoupon.map(m => m.price).reduce((last, cur) => last += cur)

console.log('[优惠券最大抵扣金额]', couponAllPrice)

function test(myCount: number) {
    const usedCoupon = getCouponPlanByLimitDiscountPriceToZero(myCount, myCoupon)
    let usedPrice = 0
    usedCoupon.forEach(c => usedPrice += c.price)
    console.log(`[总价：${myCount}块钱] 使用了${usedCoupon.length}张优惠券，一共抵扣了${usedPrice}块钱`)
    console.log(`[总价：${myCount}块钱] 优惠券大面额优先使用方案`, usedCoupon)
}

test(68)
test(66)
test(1)
test(70)
test(43)
test(5)
test(29)
test(102)
test(147)
test(198)
test(241)

// 小数精度测试
test(10.52)
test(41.85)
test(42)
test(74.14)
test(87.2)
test(148.68)
test(224.75)
test(55.95)
test(55.41)
test(28.3)