讨论/技术交流/想了一道算法题,正解还没有想明白,向各位大佬请教一下/
想了一道算法题,正解还没有想明白,向各位大佬请教一下

简介

小明预计三个月内在集换社小程序购买N元的卡片,除了购买卡片的花费之外,小程序还会对卡片收取额外的费用
收取规则如下:

  • 单月内交易额小于500 下月收取3%交易额的税率
  • 单月内交易额大于等于500 下月收取2.8%交易额的税率
  • 单月内交易额大于等于3000 下月收取2.5%交易额的税率
  • 单月内交易额大于等于10000 下月收取2.2%交易额的税率
  • 单月内交易额大于等于50000 下月收取2%交易额的税率
    假设小明开始购买的第一个月的前一月购买的卡牌交易额为0,即第一个月必须上3%税

你的算法需要输出今年小明如何安排卡牌购买计划才能上最少的税,输出只要求连续序列正确排列
例如:输入:2900
输出:[500,2400,0] 因为第一个月购买500后,剩余的2400元可以获得更低的税收,[500,500,1900]也是正确的解答

class Solution:
    def output(self, money: int) -> List[int]:


共 7 个回复

写了Java的解法,请大家看看能不能解决这个问题:

    public List<Integer> output(int money) {
        List<Integer> ans = new ArrayList<>();

        int[] taxes = new int[]{500, 3000, 10000, 50000};
        int taxIndex = 0;

        while (money > 0) {
            if (taxIndex > taxes.length - 1) {
                ans.add(money);
                break;
            }

            int curTax = taxes[taxIndex];
            if (money <= curTax) {
                ans.add(money);
                money = 0;
            } else {
                ans.add(curTax);
                money -= curTax;
                taxIndex += 1;
            }
        }
        return ans;
    }
1
//税率
var taxIndexs = []float64{
	0.03,
	0.028,
	0.025,
	0.022,
	0.02,
}
//达到税率最少交易额
var moneyIndexs = []int{
	0,
	500,
	3000,
	10000,
	50000,
}

//
// tax 目前所处税率 分为5个档次
// month 还有多少个月
// money 剩余金额
//当月花钱,要么正好达到某个税率金额,要么全花完
//当税率高时,尽量少花钱,在税率低时,要尽量多发钱,符合前面描述
func deepSearch(tax int, month int, money int) float64 {
	var minTax float64 = math.MaxFloat64
	//当前只剩一个月,只有把钱用完
	if month != 1 {
		//如果下个月要处于第0档次税率
		if money >= moneyIndexs[0]  {
			//如果下个月要处于第0档次税率,这个月最少花moneyIndexs[0]钱
			cur := deepSearch(0, month-1, money-moneyIndexs[0]) + float64(moneyIndexs[0]) * taxIndexs[tax]
			if cur < minTax {
				minTax = cur
			}
		}

		if money >= moneyIndexs[1]  {
			cur := deepSearch(1, month-1, money-moneyIndexs[1]) + float64(moneyIndexs[1]) * taxIndexs[tax]
			if cur < minTax {
				minTax = cur
			}
		}

		if money >= moneyIndexs[2]  {
			cur := deepSearch(2, month-1, money-moneyIndexs[2]) + float64(moneyIndexs[2]) * taxIndexs[tax]
			if cur < minTax {
				minTax = cur
			}
		}

		if money >= moneyIndexs[3]  {
			cur := deepSearch(3, month-1, money-moneyIndexs[3]) + float64(moneyIndexs[3]) * taxIndexs[tax]
			if cur < minTax {
				minTax = cur
			}
		}

		if money >= moneyIndexs[4]  {
			cur := deepSearch(4, month-1, money-moneyIndexs[4]) + float64(moneyIndexs[4]) * taxIndexs[tax]
			if cur < minTax {
				minTax = cur
			}
		}
	}
	//当前只剩一个月,只有把前用完
	cur := float64(money) * taxIndexs[tax]
	if cur < minTax {
		minTax = cur
	}
	return minTax
}

代码写的是go的,采用深度优先算法,调用是deepSearch(0, 3, money) ,开始税率是0档,还剩3个月,money看输入

这是一个动态规划的问题

假设只有一个月

那么无论输入多少的金额,那么税率就是:金额 * 3%

假设现在有了两个月

金额为n,第一个月支付x:

  1. 方案一:第一个月500以下为: n * 3%
  2. 方案二:第一个月500 - 3000为:x * 3% + (n-x)* 2.8% = n * 2.8% + x * 0.2%
    那么 x(>500) 为任何数:都选择第二种方案 ,且x越小越好
  3. 方案三:第一个月3000 - 10000为 x * 3% + (n-x)* 2.5% = n * 2.5% + x * 0.5%
    那么 x (> 3000) 时:可知 在此公式中,x越小越好。
    这个是时候存在一个方案二和方案一的比较,即 n* 2.8% + 100% 和 n2.5% + 1500%
    可得到:n <= 14000 % 3 ? n
    2.8% + 100% : n*2.5% + 1500%
  4. 方案四:第一个月10000 - 50000,同理得:n * 2.2 % + x * 0.8 %
    同理得: n <= 65000 % 3 ?n*2.5% + 1500% ? n * 2.2 % + 8000%
  5. 方案五:第一个月50000以上为: n*2% + x 1%
    同理得: n <= 420000%2 ? n * 2.2 % + 8000% : n
    2% + x *1%
    这时我们根据 n 的输入便可以得到最小值了吧

现在假设有三个月呢

金额为n 第一个月支付x 第二个月支付y

  1. 方案一:第一个月500以下 那么第二个月利率不变,那我为啥不第一个月一起买呢-。-!
  2. 方案二:第一个月500 - 3000 为: n * 3% + (n-x) * 2.8% + (n-x-y) * ?
    简单分析一下可得:因为第三个月利率如果大于第二个月的话,直接第二个月购买就好了,那么直接全部第二个月买就好了,这样x越大越好,当x为500时,那么第二个月开始便是2.8的利率,求二三月份的最小值。
    是不是这个问题很熟悉!参考上面就可以得出。
    我们可以得出输入一个n, 得到这里的最小值。
  3. 方案三:同上也可以得出一个最小值,只需同样比较一下。
    到这里,这个问题的答案是能够解决的。

那么假设有k个月呢?

这样我们先看看四个月
金额为n 第一个月支付x 第二个月支付y 第三个月支付 z

  1. 方案一:第一个月为500 - 3000 为 n * 3% + (n-x) * 2.8% + (n-x-y) * ? + (n-x-y-z) * ??
    简单分析一下,如果?? > ? 那么 直接全部第三个月支付即可,同样 ?> 2.8% 直接全部第二个月支付即可
    这样得到一个什么情况呢,当存在 4月支付的时候,必然是,4个月利率逐渐降低。
    且经过我们前面的推到,得到什么一个定律呢?
    任意两个相邻月(k-1,k)一定存在
  2. k-1的利率大于k的利率
  3. k-1月支付的钱一定等于k月所需税率的交易额

那下面就可以愉快的撸代码了!

public static void main(String[] args) {
    DemoApplication demoApplication = new DemoApplication();
    List<Integer> output = demoApplication.output(500000);
    System.out.println(output);

}

public List<Integer> output(int money) {
    List<Integer> ans = new ArrayList<>();
    int[] taxes = new int[]{500,500, 3000, 10000, 50000};
    if (money > 64000){
        for (int i = 0 ; i< taxes.length;i++ ){
            ans.add(taxes[i]);
        }
        ans.add(money - 64000);
    }else if (money > 14000){
        for (int i = 0 ; i< taxes.length-1;i++ ){
            ans.add(taxes[i]);
        }
        ans.add(money - 13500);
    }else if (money > 4000) {
        for (int i = 0 ; i< taxes.length-2;i++ ){
            ans.add(taxes[i]);
        }
        ans.add(money - 4000);
    }else if (money > 1000) {
        for (int i = 0 ; i< taxes.length-3;i++ ){
            ans.add(taxes[i]);
        }
        ans.add(money - 1000);
    }
    else if (money > 1000) {
        for (int i = 0 ; i< taxes.length-4;i++ ){
            ans.add(taxes[i]);
        }
        ans.add(money - 1000);
    }
    return ans;
}

哦,消费额高了,是下个月税率低

可是这样的话假如是10w元,第一个月500第二个月5w第三个月再消耗会比较少吧

看目前的题目,第一个月一定消费500,然后第二个月把剩下钱的全消费完。