2 erenfried Erenfried 于 2016.09.18 16:50 提问

优惠券算法问题,求算法帝,来一发!!

问题是这样的:有n个m元的优惠券,要结账y元,求如何最省??
例如 10元2个, 5元3个 ,3元7个;我分别结账50;28;15元;
发现当数额越小时,算最优解的偏差越多,求算法帝解决一下

//C#

using System;
using System.Collections.Generic;
using System.Linq;

namespace Calculation
{
public class Greedy
{
public string msg = "";
public string Fun(string str)
{
string res = "";
var money = Exchange(Convert.ToDecimal(str));
decimal sum = 0;
foreach (var single in money)
{
if (single.Value != 0)
{
sum += single.Key*single.Value;
string s = string.Format("{0}元---->{1}张; 共{2}元 \r\n", single.Key, single.Value, sum);
res += s;
}
}
return res + "\r\n" + sum + "-" + str + "=" + (sum - Convert.ToDecimal(str)) + "\r\n" + msg;
}
public Dictionary Money = new Dictionary();
public Dictionary SetInit(decimal a,int c)
{
//key表示钱,value表示钱的张数
Money.Add(a, c);
return Money;
}
private Dictionary Exchange(decimal num)
{
//指针
int i = 0;
int count = 1;
Dictionary ResMoney = Money.OrderByDescending(o => o.Key).ToDictionary(o => o.Key, p => p.Value);

        while (true)
        {
            #region 获取当前面值,若指针超出则直接跳出
            decimal tar;
            decimal next;
            if (i > ResMoney.Count)
            {
                //超出
                msg = "i > ResMoney.Count";
                break;
            }
            else
            {
                tar = ResMoney.Keys.ElementAt(i);  //取得面值
            }
            if (i > ResMoney.Count - 2)
            {
                next = 0;
            }
            else
            {
                next = ResMoney.Keys.ElementAt(i + 1);  //取得面值
            }

            #endregion

            if (num > tar)
            {
                num = num - tar;
                //当前面额是否用完
                if (count < ResMoney[tar])
                {
                    count++; //money的张数自增
                }
                else
                {
                    i++; //就去取下一张面值
                    if (i == ResMoney.Count)
                    {
                        msg = "num > tar";
                        break;
                    }
                    ResMoney[tar] = count;
                    count = 1;
                }
            }
            else if (num == tar)
            {
                //当余额等于当前面额时,count跳出  -4 -2 -9 -5
                ResMoney[tar] = count;
                msg = "num == tar";
                break;
            }
            else if (next < num && num < tar && next != 0)
            {
                i++; //就去取下一张面额
                if (i == ResMoney.Count)
                {
                    msg = "next < num && num < tar && next != 0";
                    break;
                }
                ResMoney[tar] = 0;
            }
            else if (num == next && next != 0)
            {
                if (tar == next)
                {
                    //余额等于最小面额,count跳出
                    ResMoney[tar] = count;
                    msg = "num == next && next != 0;tar == next";
                    break;
                }
                else
                {
                    i++; //就去取下一张面额
                    if (i == ResMoney.Count)
                    {
                        msg = "num == next && next != 0";
                        break;
                    }
                    ResMoney[tar] = 0;
                }
            }
            else if (num < next && next != 0)
            {
                //余额小于最小面额,跳出 -2 -1
                ResMoney[tar] = count;
                msg = "num < next && next != 0";  
                break;
            }
            else if (next==0)
            {
                //余额小于最小面额,跳出  -2 -7
                ResMoney[tar] = count;
                msg = "next==0";
                break;
            }
        }

        if (i < ResMoney.Count)
        {
            i++;
            for (;i<ResMoney.Count;i++)
            {
                decimal max = ResMoney.Keys.ElementAt(i);  //取得面值
                ResMoney[max] = 0;
            }
            return ResMoney; 
        }
        else
        {
            return ResMoney;
        }

    }
}

}

1个回答

caozhy
caozhy   Ds   Rxr 2016.09.18 17:25

典型的背包算法,自己google下。http://blog.csdn.net/xiaowei_cqu/article/details/8191808

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
优惠券最优使用算法
先说一下业务背景。公司做的一个投资的APP,投资金额可以用优惠券抵扣。红包面额(100,50,30,10) 优惠券使用规则: 优先使用大面额的红包,即优先使用张数最少的红包组合 优先使用有限制的红包,即优先使用有限制红包张数占比最大的组合 优先使用即将过期的红包,即优先使用平均有效期最短的组合 选择红包面额之和最大的组合(面额总值≤投资额*1%) 算法尝
基于大数据学习算法的优惠券预测模型
一、目标:预测买家是否会购买某类商品,然后将优惠券发给最有可能购买的人群,从而提升转化率和客单价。(转化率-从意向购买到实际付款;客单价-用户单次购物花费金额)二、分析:落实到算法模型上,包含两个核心的问题2.1、优惠券发给谁,即客户群选择客户群选择实际上是预测买家的购买倾向,并依据购买倾向的强弱来给出排序的结果,落实到学习模型层面来解决。这个过程我们要以用户的历史行为数据为基础,比如分析出他浏览过
机试算法讲解:第50题 动态规划之拦截导弹
/* 问题:拦截导弹。导弹系统有缺陷,后面炮弹高度<=前一发高度。计算系统能拦截多少导弹。拦截时,必须按照时间顺序,不允许先拦截后面的导弹再拦截前面的导弹。 输入:每组输入两行。第一行:导弹数量k(k<=25)。第二行:k个整数,表示第k枚导弹的高度,按时间顺序,空格分隔 输出:每组输出一行,包含一个整数,表示能拦截多少导弹。 输入: 8 300 207 155 300 299 170 158 6
算法:拦截导弹
题目描述: 某国为了防御敌国的导弹袭击,发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于等于前一发的高度。某天,雷达捕捉到敌国导弹来袭。由于该系统还在试用阶段,所以只用一套系统,因此有可能不能拦截所有的导弹。 输入第一行输入测试数据组数N(1 接下来一行输入这组测试数据共有多少个导弹m(1 接下来行输入导弹依次飞
随机优惠券发放 金额越大 概率越小金额越小概率越大算法
/**  * 金额越大 概率越小  金额越小概率越大  建议 min 和 max 的值不能相差  10以上,相差越大, 计算量越大越慢      * $pow 默认1.6 值越大 取值 1.1 到 2.0, 则分的越散 则 大金额概率越小 ,值越小  则 分的越密集 效果越差  运算越快  越大  运算量越大  * @param int $min 最小金额  * @param int $m
java组合算法应用:购物满减(任意数字组合相加在某个范围内)
任意价格相加在某个范围内package com.louisgeek.price;import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList;public class CaseTestPrice { /**
帝国竞争算法论文
英文版,帝国竞争算法,又称为殖民地竞争算法(CCA),是基于帝国主义殖民竞争机制的新优化算法,由Esmaei受帝国主义殖民竞争历史现实的启发而提出了一种新的优化算法
js或者php简单实现购买产品满1年优惠2个月的算法
最近公司网站一直在改版,从用户页面大改,到内核大改,这个过程持续快要两个月了。 现在刚改好了用户vip续费满一年优惠2个月的逻辑,觉得这部分代码很简洁明了,特分享给大家 本地测试场景是这样的:用户已经是vip4的用户了,vip4用户续费一个月花费1000元,续费一年优惠两个月花费1万元。 现在我们要处理的就是扣费这部分,js和php实现代码如下: //+======javascript=====
优惠券码生成
<?php /** * @param int $no_of_codes//定义生成优惠码个个数 * @param array $exclude_codes_array//老优惠券组 * @param int $code_length//优惠码的长度 * @return array //返回数组 */ function generate_promotion_code($no_of_code
单源最短路径算法的MapReduce实现(Metis版本)
Mapreduce 是谷歌提出的一个分布式计算框架, 利用该框架, 能够让用户方便地利用多机并行处理数据。 该框架有两个重要的函数: Map 和 Reduce, Map 函数对整个输入数据进行处理, 按照用户定义的处理方式, 从输入的数据中产生中间键值对( key, value)。Reduce 函数对这些键值对进行处理, 相同 key 的键值