题目描述

给你一个整数数组 cost 和一个整数 target。请你返回满足如下规则可以得到的 最大 整数：

• 给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
• 总成本必须恰好等于 target。
• 添加的数位中没有数字 0。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 "0"。

样例1

输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出："7772"
解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "997" 也是满足要求的数字，但 "7772" 是较大的数字。
 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

样例2

输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。

样例3

输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出："0"
解释：总成本是 target 的条件下，无法生成任何整数。

样例4

输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出："32211"

限制

• cost.length == 9
• 1 <= cost[i] <= 5000
• 1 <= target <= 5000

算法

(贪心+动态规划) $O(9 · target)$

1. 首先，要求得到最大整数，因此要拼出一个数位越长越好，高位的数字越大越好的一个数。
2. 把9个数字看作9个物品；每个数字的花费看作体积；其中target视为目标体积：这是完全背包的模型, 直白点就是从9个物品中选且体积恰好为target的所有方案。
3. 由于这里没有说每个数是多少价值, 价值可以默认为1：那么 f(i,j)就表示从前i个物品中选，且体积恰好为j的最大价值。放到题目上的意思就是：f(i,j)表示从前i个数字中选，且花费恰好为j的最大位数；
4. 最终最大位数是 f[9, target], 若最大位数为 0, 则集合中无法拼成最大整数, 返回"0"；
5. 恰好为j的情况初始化是：f(0,0) = 0, 其余为负无穷。
6. 求出所有方案之后，接下来是背包问题求具体方案或者说从f(i,j)所表示的集合中找出一组特定方案。数字尽可能要大，高位应该从数字9开始往回拼，就能找到答案。
7. 完全背包可以优化为一维状态表示。

时间复杂度

• 状态数量 x 状态计算 = $O(9 · target)$ x 常数, 时间复杂度是$O(9 · target)$

空间复杂度

• 一维状态需要开一个dp数组, 故空间复杂度为 $O(target)$

C++ 代码1(一维状态)

class Solution {
public:

    static const int M = 5010;
    int f[M];

    string largestNumber(vector<int>& v, int target) {
        memset(f, -0x3f, sizeof(f));
        f[0] = 0;

        for (int i = 0; i < 9; i ++)
            for (int j = v[i]; j <= target; j ++)
                f[j] = max(f[j], f[j - v[i]] + 1);

        if (f[target] <= 0) 
            return "0";

        // 背包问题求具体方案
        string ans;
        int j = target;
        for (int i = 8; i >= 0; i --)
            while (j >= v[i] && f[j - v[i]] + 1 == f[j]) // 用while，因为可以选无限个！
            {
                j -= v[i];
                ans += to_string(i + 1);
            }               

        return ans;
    }
};

C++ 代码2(二维状态)

ps: 用二维状态的代码会慢很多, 弄懂了一维其实一维更好写

时间复杂度

• 状态数量 x 状态计算 = $O(9 · target)$ x $O(target)$, 时间复杂度是$O(9 · target²)$
  完全背包的时间复杂度不太清楚是不是这样算, 有知道的告诉我hh

空间复杂度

• 二维状态需要开一个dp数组, 故空间复杂度为 $O(9 · target)$

class Solution {
public:

    static const int N = 10, M = 5010;
    int f[N][M];

    string largestNumber(vector<int>& cost, int m) {
        memset(f, -0x3f, sizeof(f));
        f[0][0] = 0;

        for (int i = 1; i <= 9; i ++)
            for (int j = 0; j <= m; j ++) {
                f[i][j] = f[i - 1][j];
                int v = cost[i - 1];
                for (int k = 1; k <= j / v; k ++)
                    f[i][j] = max(f[i][j], f[i - 1][j - v * k] + k);
            }

        if (f[9][m] <= 0)
            return "0";

        int j = m;
        string ans;
        for (int i = 9; i >= 1; i --)
        {
            int v = cost[i - 1];
            for (int k = j / v; k >= 0; k --) // 每个物品一次性拿最完k个, 一个个拿和一次性拿是一样的
            {
                //注意：二维状态用的是f[i][j - v * k]这一层，而不是f[i-1][j - v * k]
                if (f[i][j - v * k] + k == f[i][j])
                {
                    j -= v * k;
                    while(k --) 
                        ans += to_string(i);

                    break;
                }                  
            }
        }

        return ans;
    }
};