王者荣耀虎年充值—

整活简介

今天是农历除夕，王者荣耀一年一度的 ~~割韭菜~~ 年限皮肤又上场了。

打开游戏，进入充值页面，开冲！

嗯？等等，好像要破费？！

虽然APP Store有充值赠送机制，但当我需要的目标数额多起来时，怎么获取最优化的充值方案呢？似乎是个有趣的问题 😼

所谓 最优化的充值方案 ，即是指两种情况：

花费最少的钱，获取目标数额的点券；
在一定量的花销下，获取最多的点券。

这两种情景不一样哈！第一个是在满足购买需求的情况下尽可能少地花钱！第二个是在预算有限的情况下尽可能多地买到点券！

场景一、购买一定点券，计算最少花销

场景一就是当我们需要一定数量的点券时，计算最少的花销是多少！这个场景很有意义！因为在充钱的时候，大多数情况就是这个场景！我们不会去考虑这次要冲多少钱，而是首先考虑这次要买的是什么东西。

既然文章标题都已经点明了我的用意，那就直接从DP的角度开始思考了 😏

令 dp[i] 表示 购买 i 点券的最少花销 ，那么对于目标点券 i ，它可以由上图中所有可能的方案组成。例如我们需要购买 1430 点券，那么我们可以花费若干个 1￥ 购买若干份 10点券 ，也可以花费两个 68￥ 购买两份 715(680+35)点券 。唯一的限制是，不能使用比 i 更大的购买方案，例如我们需要 1430 点券，那就不能花费 648￥ 去买到六千多点券，不然就很浪费！

既然要使用DP，那么我们得到的状态转移方程应该是什么呢？

这是个很简单的问题！假如我们使用的购买方案是 m ， cost[m] 表示使用 m 号购买方案 花费的RMB ，gain[m] 表示使用 m 号购买方案 获得的点券 ，而 dp[i] 仍然是 购买 i 点券的最少花销 ，那么： $$ dp[i] = min(dp[i], dp[i - gain[m]] + cost[m]) $$ 其实就是：假如我们选择了方案 m ，获得了gain[m] 的点券，花掉了 cost[m] 的钱，还要继续获得 i - gain[m] 的点券，这个 i - gain[m] 点券的最少花销应该是此前已经计算过的了！那么总的花销就是 dp[i - gain[m]] + cost[m] 啦！

我们要考虑的是最优的方案，只要要把所有符合条件的方案 m 循环一遍即可。

根据以上的分析，开始真正的DP过程，需要注意的是：

可以看到APP Store里面所有的购买方案中，即便考虑了赠送的点券，获取到的点券也都是 5 的倍数。
目标点券有可能无法恰好获取，此时必须容许一定程度的上溢，例如我只希望购买 888 点券，但这个数额不是 5 的倍数，因此我可能需要购买 890 的点券。

void minCostToGetTargetPoints(int targetPoints)
{
    int i;
    vector<int> dp(targetPoints + 61, DP_MAX);
    dp[10] = 1;  // 10 Points 1 RMB
    dp[0] = 0;

    for (i = 10; i <= targetPoints + 60; i += 5)
    {
        int m = 0;
        while (gain[m] <= i)
        {
            dp[i] = min(dp[i], dp[i - gain[m]] + cost[m]);
            m++;
        }
    }

    printResultByTargetPoints(dp, targetPoints);

    return ;
}

void printResultByTargetPoints(vector<int>& dp, int targetPoints)
{
    int i = targetPoints;
    // 首先要找到第一个可用的方案
    while (dp[i] == DP_MAX) i++;
    // 之后开始打印上溢 60 点券之内的方案
    while (i < dp.size())
    {
        if (dp[i] == DP_MAX)
        {
            i += 5;
            continue;
        }
        cout << "Cost " << dp[i] << " yuan to get " << i << " points.\n";
        i += 5;
    }

    return ;
}

在上面这部分代码中，有几个细节：

允许上溢 60 点券，即我本来可能需要买 220 点券，但可以计算到购买 280 点券的最优解；
因为能买到的点券额度一定是 5 的倍数，因此DP时直接将 i += 5 ；
对于无解的情况，例如购买 13 个点券这种情况， dp[13] 一定等于原始的 DP_MAX ，这种情况正如此前所说，要发生上溢，也就是在输出答案的时候先把 i 一直往上增加，直到 dp[i] != DP_MAX 为止！

直接尝试执行一下！

#define DP_MAX 0xffff

vector<int> cost = { 1, 6, 45, 68, 118, 198, 348, 648 };
vector<int> gain = { 10, 60, 475, 715, 1240, 2100, 3690, 6868 };

int main() {
    minCostToGetTargetPoints(2140);
}

/*
执行完成，耗时：0 ms
Cost 202 yuan to get 2140 points.
Cost 204 yuan to get 2145 points.
Cost 203 yuan to get 2150 points.
Cost 205 yuan to get 2155 points.
Cost 204 yuan to get 2160 points.
Cost 206 yuan to get 2165 points.
Cost 205 yuan to get 2170 points.
Cost 207 yuan to get 2175 points.
Cost 206 yuan to get 2180 points.
Cost 208 yuan to get 2185 points.
Cost 207 yuan to get 2190 points.
Cost 209 yuan to get 2195 points.
Cost 208 yuan to get 2200 points.
*/

难受了！这是什么输出啊？？我只知道要获得目标点券最少需要多少元，但是程序没告诉我具体的充值方案！

看来需要一个额外的变量来告诉我最近的一次充值是多少数额，然后我逐渐往回递推，获得总的充值方案。

新增一个小功能，要额外花费不少代码行：

void minCostToGetTargetPoints(int targetPoints)
{
    int i;
    vector<int> dp(targetPoints + 61, DP_MAX);
    vector<int> lastTopup(targetPoints + 61, DP_MAX);
    dp[10] = 1;  // 10 Points 1 RMB
    dp[0] = 0;

    for (i = 10; i <= targetPoints + 60; i += 5)
    {
        int m = 0;
        while (gain[m] <= i)
        {
            if (dp[i] >= dp[i - gain[m]] + cost[m])
            {
                dp[i] = dp[i - gain[m]] + cost[m];
                // 新增：保存一下最后一次充值购买的方案
                lastTopup[i] = m;
            }
            m++;
        }
    }

    printResultByTargetPoints(dp, lastTopup, targetPoints);

    return ;
}

void printResultByTargetPoints(vector<int>& dp, vector<int>& lastTopup, int targetPoints)
{
    int i = targetPoints;
    // 首先要找到第一个可用的方案
    while (dp[i] == DP_MAX) i++;
    // 之后开始打印上溢 60 点券之内的方案
    while (i < dp.size())
    {
        if (dp[i] == DP_MAX)
        {
            i += 5;
            continue;
        }
        cout << "Cost " << dp[i] << " yuan to get " << i << " points.\n";
        cout << "The method is : \n\tcost(￥)\tpoints\n";
        for (int tmp = i; tmp > 0; )
        {
            int m = lastTopup[tmp];
            cout << "\t" << cost[m] << "\t\t" << gain[m] << "\n";
            tmp -= gain[m];
        }
        i += 5;
    }
}

执行一下！

#define DP_MAX 0xffff

vector<int> cost = { 1, 6, 45, 68, 118, 198, 348, 648 };
vector<int> gain = { 10, 60, 475, 715, 1240, 2100, 3690, 6868 };

int main() {
    minCostToGetTargetPoints(2140);
}

/*
执行完成，耗时：0 ms
Cost 202 yuan to get 2140 points.
The method is : 
    cost(￥)    points
    198        2100
    1        10
    1        10
    1        10
    1        10
Cost 204 yuan to get 2145 points.
The method is : 
    cost(￥)    points
    68        715
    68        715
    68        715
Cost 203 yuan to get 2150 points.
The method is : 
    cost(￥)    points
    198        2100
    1        10
    1        10
    1        10
    1        10
    1        10
Cost 205 yuan to get 2155 points.
The method is : 
    cost(￥)    points
    68        715
    68        715
    68        715
    1        10
Cost 204 yuan to get 2160 points.
The method is : 
    cost(￥)    points
    198        2100
    6        60
======= 此处省略若干行 =======
*/

从上面这个例子的输出可以看到：同样的 204￥ ，有的方案可以买到 2145 点券，而有的能买到 2160 点券！差了一块多！因此我们不能只打印目标点券的最优解，往上多打印几个，可能发现用相同的钱可以买到更多点券，何乐不为呢 😹

场景二、固定一定花销，购买最多点券

场景一是比较常见的，至于场景二，手头比较拮据的时候用吧！

这个场景就是个典型的 完全背包问题 而已：令 dp[j] 表示花费 j 元钱能买到的最多点券，那么对于所有可行的方案 m ，转移方程就是： $$ dp[i] = max(dp[i], dp[i - cost[m]] + gain[m]) $$ 其实两个场景思路差不多，直接上代码！

void maxPointsByMaxCost(int maxCost)
{
    int j = 0;
    vector<int> dp(maxCost + 1, 0);
    vector<int> lastPurchase(maxCost + 1, 0);

    for (j = 0; j <= maxCost; j++)
    {
        int m = 0;
        while (cost[m] <= j)
        {
            if (dp[j] <= dp[j - cost[m]] + gain[m])
            {
                dp[j] = dp[j - cost[m]] + gain[m];
                lastPurchase[j] = m;
            }
            m++;
        }
    }

    printResultByMaxCost(dp, lastPurchase, maxCost);

    return ;
}

void printResultByMaxCost(vector<int>& dp, vector<int>& lastPurchase, int& maxCost)
{
    cout << "You can get " << dp[maxCost] << " points using " << maxCost << " yuan.\n";
    cout << "The method is: \n\tCost(￥)\tPoints\n";
    for (int tmp = maxCost; tmp > 0; )
    {
        int m = lastPurchase[tmp];
        cout << "\t" << cost[m] << "\t" << gain[m] << "\n";
        tmp -= cost[m];
    }

    return ; 
}

执行一下：

#define DP_MAX 0xffff

vector<int> cost = { 1, 6, 45, 68, 118, 198, 348, 648 };
vector<int> gain = { 10, 60, 475, 715, 1240, 2100, 3690, 6868 };

int main() {
    // minCostToGetTargetPoints(2135);
    maxPointsByMaxCost(499);
    maxPointsByMaxCost(200);
    maxPointsByMaxCost(20);
}

/*
执行完成，耗时：0 ms
You can get 5280 points using 499 yuan.
The method is: 
    Cost(￥)    Points
    198    2100
    198    2100
    45    475
    45    475
    6    60
    6    60
    1    10
You can get 2120 points using 200 yuan.
The method is: 
    Cost(￥)    Points
    198    2100
    1    10
    1    10
You can get 200 points using 20 yuan.
The method is: 
    Cost(￥)    Points
    6    60
    6    60
    6    60
    1    10
    1    10
*/

总的代码

#define DP_MAX 0xffff

vector<int> cost = { 1, 6, 45, 68, 118, 198, 348, 648 };
vector<int> gain = { 10, 60, 475, 715, 1240, 2100, 3690, 6868 };

void printResultByTargetPoints(vector<int>& dp, vector<int>& lastTopup, int targetPoints);

void minCostToGetTargetPoints(int targetPoints)
{
    int i;
    vector<int> dp(targetPoints + 61, DP_MAX);
    vector<int> lastTopup(targetPoints + 61, DP_MAX);
    dp[10] = 1;  // 10 Points 1 RMB
    dp[0] = 0;

    for (i = 10; i <= targetPoints + 60; i += 5)
    {
        int m = 0;
        while (gain[m] <= i)
        {
            if (dp[i] >= dp[i - gain[m]] + cost[m])
            {
                dp[i] = dp[i - gain[m]] + cost[m];
                // 新增：保存一下最后一次充值购买的方案
                lastTopup[i] = m;
            }
            m++;
        }
    }

    printResultByTargetPoints(dp, lastTopup, targetPoints);

    return ;
}

void printResultByTargetPoints(vector<int>& dp, vector<int>& lastTopup, int targetPoints)
{
    int i = targetPoints;
    // 首先要找到第一个可用的方案
    while (dp[i] == DP_MAX) i++;
    // 之后开始打印上溢 60 点券之内的方案
    while (i < dp.size())
    {
        if (dp[i] == DP_MAX)
        {
            i += 5;
            continue;
        }
        cout << "Cost " << dp[i] << " yuan to get " << i << " points.\n";
        cout << "The method is : \n\tcost(￥)\tpoints\n";
        for (int tmp = i; tmp > 0; )
        {
            int m = lastTopup[tmp];
            cout << "\t" << cost[m] << "\t\t" << gain[m] << "\n";
            tmp -= gain[m];
        }
        i += 5;
    }
}

void printResultByMaxCost(vector<int>& dp, vector<int>& lastPurchase, int& maxCost);
void maxPointsByMaxCost(int maxCost)
{
    int j = 0;
    vector<int> dp(maxCost + 1, 0);
    vector<int> lastPurchase(maxCost + 1, 0);

    for (j = 0; j <= maxCost; j++)
    {
        int m = 0;
        while (cost[m] <= j)
        {
            if (dp[j] <= dp[j - cost[m]] + gain[m])
            {
                dp[j] = dp[j - cost[m]] + gain[m];
                lastPurchase[j] = m;
            }
            m++;
        }
    }

    printResultByMaxCost(dp, lastPurchase, maxCost);

    return ;
}

void printResultByMaxCost(vector<int>& dp, vector<int>& lastPurchase, int& maxCost)
{
    cout << "You can get " << dp[maxCost] << " points using " << maxCost << " yuan.\n";
    cout << "The method is: \n\tCost(￥)\tPoints\n";
    for (int tmp = maxCost; tmp > 0; )
    {
        int m = lastPurchase[tmp];
        cout << "\t" << cost[m] << "\t" << gain[m] << "\n";
        tmp -= cost[m];
    }

    return ; 
}

int main() {
    minCostToGetTargetPoints(2135);
    maxPointsByMaxCost(499);
    maxPointsByMaxCost(200);
    maxPointsByMaxCost(20);
}

我用了LeetCode的 playground 功能，因此这个代码就没有头函数之类了~

在最后，今年我希望购买鲁班和孙膑的皮肤，可能还需要进阶一下战令！总共需要 1430+710+388 = 2528 点券。我的程序告诉我：

/*
执行完成，耗时：0 ms
Cost 241 yuan to get 2530 points.
The method is : 
    cost(￥)    points
    198        2100
    6        60
    6        60
    6        60
    6        60
    6        60
    6        60
    6        60
    1        10
Cost 241 yuan to get 2535 points.
The method is : 
    cost(￥)    points
    45        475
    45        475
    45        475
    45        475
    45        475
    6        60
    6        60
    1        10
    1        10
    1        10
    1        10
Cost 242 yuan to get 2540 points.
The method is : 
    cost(￥)    points
    198        2100
    6        60
    6        60
    6        60
    6        60
    6        60
    6        60
    6        60
    1        10
    1        10
Cost 242 yuan to get 2545 points.
The method is : 
    cost(￥)    points
    45        475
    45        475
    45        475
    45        475
    45        475
    6        60
    6        60
    1        10
    1        10
    1        10
    1        10
    1        10
===== 省略若干行 =====
*/

看来我得花掉 241￥ ，真是一笔大数目 😿

同时，我的程序还告诉我，241元最多可以获取到：

/*
执行完成，耗时：0 ms
You can get 2535 points using 241 yuan.
The method is: 
    Cost(￥)    Points
    45        475
    45        475
    45        475
    45        475
    45        475
    6        60
    6        60
    1        10
    1        10
    1        10
    1        10
You can get 2575 points using 243 yuan.
The method is: 
    Cost(￥)    Points
    198        2100
    45        475
*/

诶？多花2块钱，即243元，能够多获取 40 点券？

我先去充钱了朋友们~