游戏合成装备算法面试题

**

更新时间：2020-09-14

**

最近很多游戏公司来招聘，下面给出面试到的算法题。
我也不懂，为啥这么多游戏公司缺人。
而且我也没做过游戏方面啊！！！！

面试内容：
下图是一个装备系统的合成图谱，箭头指向的是合成之后的装备，每合成一个装备需要消耗一些金币（标注在矩形框里面），箭头上的数字表示合成所需的材料数量。比如，要合成n个装备A，需要消耗3n个装备B、1n个装备C、4n个装备D，而且还需要消耗26n金币（装备B和装备D的合成与此类似）。
为了简单起见，下面题目的装备图谱都是一棵多叉树，而且玩家最初只拥有指定数量的叶子节点的装备，也就是图中的装备C、装备E、装备F和装备G。
注意，下面的图谱只是一个例子，作答的时候不要局限于这个图谱。

已知玩家拥有一些初级装备（叶子节点的装备）和n个金币，并且所有装备的合成都需要消耗金币，玩家需要合成尽可能多的某个装备（记为装备X），请用C#语言（后端用c++语言）计算出玩家最多可以合成出多少个装备X。

请在收到题目的一至两天内完成，提交的时候只需要提交源代码以及算法思路。为了规范输入输出，下面给出代码的基本结构，作答的时候不要修改Run函数的函数原型。

public class Exam
{
public class MaterialData
{
public ItemData item; //合成所需的物品
public int count; //合成所需的该物品的数量
}

public class ItemData
{
public int id; //物品 ID
public int count;//当前拥有的物品数量
public int costGold;//合成该物品所需的金币
public List materialList; //合成该物品所需的材料
}

///
/// 计算用 totalGold 金币最多可以合成的 item 装备的数量
///
/// 要合成的装备
/// 拥有的金币
/// 可合成的 item 装备的最大数量
public int Run(ItemData item, int totalGold)
{
return 0;
}
}

其实就是大部分游戏材料合成的算法操作。
玩过网游或者王者的人应该都知道。

代码：测试数据和注释写的挺清楚的。（我也是参考别人的）
可能在暗示我不是做游戏这方面的料吧。
说到这，C#写法和java简直就是一模一样。有点不习惯。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


//目标：
//输入:指定合成的装备
//输出:可合成数量
//条件：金币够，材料够
public class Exam
{
    //物品所需材料
    public class MaterialData
    {
        public ItemData item;   //合成所需的物品
        public int count;       //合成所需的该物品的数量
    }
    //该物品
    public class ItemData
    {
        public int id;  //物品 ID
        public int count;//当前拥有的物品数量
        public int costGold;//合成该物品所需的金币
        public List<MaterialData> materialList; //合成该物品所需的材料
    }

    //满足条件--这句没用上，原本以为是要问能买多少个A
    public int equivalence(int numE, int numF, int numC, int numG,int totalGold)
    {
        int numA=0, numB=0, numD=0;
        int money = totalGold;
        int allMoney = totalGold;

        //满足B--至少能买一个
        if (numE > 0 && numF > 0 && money >= 53)
        {
            //计算材料够合成几个
            int[] array = { numE, numF };
            Array.Sort(array);
            int min = array[array.Length - 1];

            int moneyCanBuyNum = money / 53;
            if(moneyCanBuyNum >= min)//如果钱多，材料够了，买足材料的物品
            {
                numB = min;
                money = money - 53 * min;
            }
            else//钱不够，材料够了
            {
                numB = moneyCanBuyNum;
                money = money - 53 * moneyCanBuyNum;
            }
        }

        //满足D--至少能买一个
        if (numG > 0  && money >= 58)
        {
            int moneyCanBuyNum = money / 58;
            if (moneyCanBuyNum >= numG)//钱多，材料够了，买足材料的物品
            {
                numD = numG;
                money = money - 58 * numG;
            }
            else//钱不够，材料够了
            {
                numD = moneyCanBuyNum;
                money = money - 58 * moneyCanBuyNum;
            }
        }
        //满足A
        if (numB > 0 && numD > 0 && numC > 0 && money >= 26)
        {
            int[] array = { numB, numC, numD };
            Array.Sort(array);
            int min = array[array.Length - 1];

            int moneyCanBuyNum = money / 26;
            if (moneyCanBuyNum >= min)//如果钱多，材料够了，买足材料的物品
            {
                numA = min;
                money = money - 26 * min;
            }
            else//钱不够，材料够了
            {
                numA = moneyCanBuyNum;
                money = money - 26 * moneyCanBuyNum;
            }
        }
        Console.WriteLine("{0},{1},{2},{3}", numA,numB, numD,money);

        return 0;
    }

    //递归获取该物体最多可合成数量
    private int getSynthesisCount(ItemData item)
    {
        //获取物品所需材料品种数量--G and more
        int speciesNum = item.materialList.Count;
        Console.WriteLine("species num:" + speciesNum);

        //如果材料种类为0，代表为节点，返回当前材料数量
        if (speciesNum == 0)
        {
            return item.count;
        }
        int materialCount, canNum;
        int minCount = int.MaxValue;
        Console.WriteLine("minCount num:" + minCount);

        for (int i = 0; i < speciesNum; i++)
        {
            //该材料是否还有下一级材料
            materialCount = getSynthesisCount(item.materialList[i].item);
            Console.WriteLine("G num:" + materialCount);

            //合成材料数 / 所需材料数量 = 物品
            canNum = materialCount / item.materialList[i].count;
            Console.WriteLine("materialCount num:" + canNum);

            minCount = Math.Min(minCount, canNum);
        }
        return minCount;
    }

    //递归获取该物体合成价格
    private int getSynthesisCost(ItemData item)
    {
        //获取物品所需材料品种数量--G and more
        int speciesNum = item.materialList.Count;
        Console.WriteLine("species num:" + speciesNum);

        if (speciesNum == 0)
        {
            return 0;
        }
        int minCount = 0;
        for (int i = 0; i < speciesNum; i++)
        {
            //
            minCount += getSynthesisCost(item.materialList[i].item) * item.materialList[i].count;
        }
        minCount += item.costGold;
        //返回总共的合成花费
        return minCount;
    }

    private int getMaxNum(int canSynthesisNum,int canMoneyNum ,int money)
    {
        int num = 0;
        int moneyCanBuyNum = money / canMoneyNum;
        if (moneyCanBuyNum >= canSynthesisNum)//如果钱多，材料够了，买足材料的物品
        {
            num = canSynthesisNum;
            money = money - canMoneyNum * canSynthesisNum;
        }
        else//钱不够，材料够了
        {
            num = moneyCanBuyNum;
            money = money - canMoneyNum * moneyCanBuyNum;
        }
        Console.WriteLine("money:" + money);

        return num;
    }


    /// <summary>
    /// 计算用 totalGold 金币最多可以合成的 item 装备的数量
    /// </summary>
    /// <param name="item">要合成的装备</param>
    /// <param name="totalGold">拥有的金币</param>
    /// <returns>可合成的 item 装备的最大数量</returns>
    public int Run(ItemData item, int totalGold)
    {
        int canSynthesisNum = getSynthesisCount(item);
        Console.WriteLine("Synthesis can buy Num:" + canSynthesisNum);

        int canMoneyNum = getSynthesisCost(item);
        Console.WriteLine("money Synthesis price:" + canMoneyNum);

        Console.WriteLine("Max Num:" + getMaxNum(canSynthesisNum, canMoneyNum, totalGold)); 

        return 0;
    }
}


namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            //例子为合成D
            Exam.ItemData TestData()
            {
                //D
                Exam.ItemData itemData = new Exam.ItemData();
                itemData.id = 10004;
                itemData.count = 0;
                itemData.costGold = 58;
                itemData.materialList = new List<Exam.MaterialData>();
                itemData.materialList.Add(BoxG());
                return itemData;
            }
            Exam.MaterialData BoxG()
            {
                //所需材料2个G
                Exam.MaterialData material = new Exam.MaterialData();
                material.count = 2;

                //G的拥有量
                Exam.ItemData itemG = new Exam.ItemData();
                itemG.count = 6;
                itemG.id = 10007;
                itemG.costGold = 0;
                material.item = itemG;
                itemG.materialList = new List<Exam.MaterialData>();
                return material;
            }


            Exam ee = new Exam();
            Exam.ItemData item = TestData();
            
            ee.Run(item, 100);




        }
    }
}

本文地址：https://blog.csdn.net/weixin_44353958/article/details/108576921