记一道“芯片升级消耗”数学题

　　　　　　　　

要求

• 现有一堆特殊芯片和普通芯片，芯片等级分为0-6级，芯片都可以合成升级，普通芯片和特殊芯片升级都消耗一定钱数和同等级普通芯片数。配置表如上，比如：升级一个0级特殊芯片到1级，需要消耗自身和2个0级普通芯片共3个芯片，花费为1；升级一个1级普通芯片到2级，需要消耗自身和2个1级普通芯片共3个芯片，花费为2。这里只讨论升级特殊芯片。要求实现设计图所示所有功能。

实现思路

• 首先把特殊芯片和普通芯片分类，因为6级已是满级无法再升级，所以特殊芯片中再去除6级芯片，剩下的特殊芯片都是有可能升级的芯片。
• “合成等级”默认比芯片自身高一级，最低比芯片自身高一级，最高为6级。
• “合成数量” 默认为1，实际数量多少后面程序会修正。
• 根据前面的“合成等级”和“合成数量”，再计算出“花费”具体数。
• 界面初始化时，程序会计算所有特殊芯片的“合成等级”和“合成数量”，如果某芯片无法升级，会修正该芯片“合成数量”为0，“花费”为0。
• 点击某芯片“合成等级”或“合成数量”加减按钮，该芯片前的所有芯片“合成等级”、“合成数量”数不变，而它后面所有芯片的“合成等级”不变，“合成数量”数需要程序修正，如果仍可升级则不变，否则数量减1尝试升级，如果仍不能升级则继续减1尝试，直至数量为0。例如，可升级特殊芯片依次为A、B、C、D，将B的“合成数量”加1，A的“合成等级”、“合成数量”数不动，C、D的“合成等级”不动、“合成数量”程序修正。

讨论重点

• 这里主要讨论：在普通芯片数量有限的前提下，特殊芯片的升级消耗普通芯片数量算法和花费算法。
• 测试用例：普通芯片消耗库有100个0级普通芯片，1个1级普通芯片，1个2级普通芯片。现有1个0级特殊芯片，尝试合成等级为3级，合成数量为1。
• 首先，初始化配置表和普通芯片消耗库，这里用Dictionary<int, int>简单实现。cfg_num的key为等级，value为消耗芯片数；cfg_cost的key为等级，value为花费。

Dictionary<int, int> cfg_num = new Dictionary<int, int>();
Dictionary<int, int> cfg_cost = new Dictionary<int, int>();
Dictionary<int, int> expDic = new Dictionary<int, int>();

public void InitCfg()
{
    // 所需消耗数量配置
    cfg_num = new Dictionary<int, int>();
    cfg_num[0] = 3;
    cfg_num[1] = 3;
    cfg_num[2] = 3;
    cfg_num[3] = 3;
    cfg_num[4] = 3;
    cfg_num[5] = 3;
    cfg_num[6] = 0;

    // 花费配置
    cfg_cost = new Dictionary<int, int>();
    cfg_cost[0] = 1;
    cfg_cost[1] = 2;
    cfg_cost[2] = 3;
    cfg_cost[3] = 4;
    cfg_cost[4] = 5;
    cfg_cost[5] = 6;
    cfg_cost[6] = 0;

}

// 初始化普通芯片消耗库
public void InitExpDic()
{
    expDic[0] = 100;
    expDic[1] = 1;
    expDic[2] = 1;
    expDic[3] = 0;
    expDic[4] = 0;
    expDic[5] = 0;
    expDic[6] = 0; // 6级普通芯片数目肯定是0

}

• 将要求合成等级的特殊芯片全部转化为0级芯片，得到所要消耗0级芯片总数即“总消耗”。将初始特殊芯片自身全部转化为0级芯片，普通芯片消耗库符合部分也全部转化为0级芯片，两者相加得到“总拥有”。当总拥有 >= 总消耗，即可升级。

public bool CanUp(int needLv, int needNum, int itsLv)
{
    if (needLv == 0 || needNum == 0)
    {
        return true;
    }
    // 总消耗
    Dictionary<int, int> costDic = new Dictionary<int, int>();
    for (int i = 0; i <= 6; i++)
    {
        costDic[i] = 0;
    }
    costDic[needLv] = needNum;
    // 总拥有 = 普通芯片消耗库符合部分 + 自身
    Dictionary<int, int> gotDic = new Dictionary<int, int>();
    for (int i = 0; i <= 6; i++)
    {
        gotDic[i] = expDic[i];
    }
    gotDic[itsLv] += 1;
    int costZeroNum = GetZeroNum(costDic, needLv, 0);
    int gotZeroNum = GetZeroNum(gotDic, needLv - 1, 0);
    return gotZeroNum >= costZeroNum;
    
}

public int GetExpDicZeroSum()
{
    return GetZeroNum(expDic, 6, 0);
}

// 从level开始往前，所有芯片都转换成0级普通芯片
public int GetZeroNum(Dictionary<int, int> dic, int level, int extraNum)
{
    if (level == 0)
    {
        return dic[0] + extraNum;
    }
    int num = (dic[level] + extraNum) * cfg_num[level - 1];
    return GetZeroNum(dic, level - 1, num);

}

• 花费算法如下，因为该算法会真正扣去普通芯片库的相关数量，所以需要确定特殊芯片能升级再使用。

// 能升级再算花费
public int ApplyCost(Dictionary<int, int> expDic, int needLv, int needNum, int itsLv)
{
    if (needNum <= 0 || needLv == 0)
    {
        return 0;
    }
    int cost = needNum * cfg_cost[needLv - 1];
    int num = cfg_num[needLv - 1];
    if (itsLv == needLv - 1)
    {
        num -= 1;
    }
    int leftNum = needNum * cfg_num[needLv - 1] - expDic[needLv - 1];
    if (itsLv == needLv - 1)
    {
        leftNum -= 1;
    }
    if (leftNum > 0)
    {
        expDic[needLv - 1] = 0;
    }
    else
    {
        expDic[needLv - 1] = Math.Abs(leftNum);
    }
    cost += ApplyCost(expDic, needLv - 1, leftNum, itsLv);
    return cost;
    
}

• 测试用例如下

public void Test()
{
    InitCfg();
    InitExpDic();
    PrintExpDic();
    Console.WriteLine();
    int itsLv = 0;
    int needLv = 3;
    int needNum = 1;
    Console.WriteLine("{0}级特殊芯片，合成等级：{1}级，合成数量：{2}个", itsLv, needLv, needNum);
    if (CanUp(needLv, needNum, itsLv))
    {
        Console.WriteLine("合成成功");
        int cost = ApplyCost(expDic, needLv, needNum, itsLv);
        Console.WriteLine("共花费: {0}", cost);
        PrintExpDic();
    }
    else
    {
        Console.WriteLine("合成失败");
    }
}

• 得到打印如下，“1个0级特殊芯片，尝试合成等级为3级，合成数量为1”，需要14个0级普通芯片，1个1级芯片，1个2级普通芯片。

• 全部代码如下

using System;
using System.Collections.Generic;

namespace CanDDel
{
    public class Solution
    {
        Dictionary<int, int> cfg_num = new Dictionary<int, int>();
        Dictionary<int, int> cfg_cost = new Dictionary<int, int>();
        Dictionary<int, int> expDic = new Dictionary<int, int>();

        public void Test()
        {
            InitCfg();
            InitExpDic();
            PrintExpDic();
            Console.WriteLine();
            int itsLv = 0;
            int needLv = 3;
            int needNum = 1;
            Console.WriteLine("{0}级特殊芯片，合成等级：{1}级，合成数量：{2}个", itsLv, needLv, needNum);
            if (CanUp(needLv, needNum, itsLv))
            {
                Console.WriteLine("合成成功");
                int cost = ApplyCost(expDic, needLv, needNum, itsLv);
                Console.WriteLine("共花费: {0}", cost);
                Console.WriteLine();
                PrintExpDic();
            }
            else
            {
                Console.WriteLine("合成失败");
            }
        }

        public void InitCfg()
        {
            // 所需消耗数量配置
            cfg_num = new Dictionary<int, int>();
            cfg_num[0] = 3;
            cfg_num[1] = 3;
            cfg_num[2] = 3;
            cfg_num[3] = 3;
            cfg_num[4] = 3;
            cfg_num[5] = 3;
            cfg_num[6] = 0;

            // 花费配置
            cfg_cost = new Dictionary<int, int>();
            cfg_cost[0] = 1;
            cfg_cost[1] = 2;
            cfg_cost[2] = 3;
            cfg_cost[3] = 4;
            cfg_cost[4] = 5;
            cfg_cost[5] = 6;
            cfg_cost[6] = 0;

        }

        // 初始化普通芯片消耗库
        public void InitExpDic()
        {
            expDic[0] = 100;
            expDic[1] = 1;
            expDic[2] = 1;
            expDic[3] = 0;
            expDic[4] = 0;
            expDic[5] = 0;
            expDic[6] = 0; // 6级普通芯片数目肯定是0

        }

        public bool CanUp(int needLv, int needNum, int itsLv)
        {
            if (needLv == 0 || needNum == 0)
            {
                return true;
            }
            // 总消耗
            Dictionary<int, int> costDic = new Dictionary<int, int>();
            for (int i = 0; i <= 6; i++)
            {
                costDic[i] = 0;
            }
            costDic[needLv] = needNum;
            // 总拥有 = 普通芯片消耗库 + 自身
            Dictionary<int, int> gotDic = new Dictionary<int, int>();
            for (int i = 0; i <= 6; i++)
            {
                gotDic[i] = expDic[i];
            }
            gotDic[itsLv] += 1;
            int costZeroNum = GetZeroNum(costDic, needLv, 0);
            int gotZeroNum = GetZeroNum(gotDic, needLv, 0);
            return gotZeroNum >= costZeroNum;

        }

        public int GetExpDicZeroSum()
        {
            return GetZeroNum(expDic, 6, 0);

        }

        // 从level开始往前，所有芯片都转换成0级普通芯片
        public int GetZeroNum(Dictionary<int, int> dic, int level, int extraNum)
        {
            if (level == 0)
            {
                return dic[0] + extraNum;
            }
            int num = (dic[level] + extraNum) * cfg_num[level - 1];
            return GetZeroNum(dic, level - 1, num);

        }

        // 能升级再算花费
        public int ApplyCost(Dictionary<int, int> expDic, int needLv, int needNum, int itsLv)
        {
            if (needNum <= 0 || needLv == 0)
            {
                return 0;
            }
            int cost = needNum * cfg_cost[needLv - 1];
            int num = cfg_num[needLv - 1];
            if (itsLv == needLv - 1)
            {
                num -= 1;
            }
            int leftNum = needNum * cfg_num[needLv - 1] - expDic[needLv - 1];
            if (itsLv == needLv - 1)
            {
                leftNum -= 1;
            }
            if (leftNum > 0)
            {
                expDic[needLv - 1] = 0;
            }
            else
            {
                expDic[needLv - 1] = Math.Abs(leftNum);
            }
            cost += ApplyCost(expDic, needLv - 1, leftNum, itsLv);
            return cost;

        }

        public void PrintExpDic()
        {
            Console.WriteLine("普通芯片库当前数量:");
            foreach (KeyValuePair<int, int> item in expDic)
            {
                Console.WriteLine("等级:{0}, 数量:{1}", item.Key, item.Value);
            }

        }

    }
    
}