（完全背包）Leetcode1449. 数位成本和为目标值的最大数字

传送门

题目描述

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

给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。

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

样例

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

输入：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

思路

代码

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        //先计算出最大多少位——完全背包
        vector<vector<int>> dp(10, vector<int>(target+1,INT_MIN));
        vector<vector<int>> from(10,vector<int>(target+1));
        dp[0][0] = 0;
        for(int i = 1; i<=9; i++)
        {
            for(int j = 0; j<=target; j++)
            {
                if(j < cost[i-1])
                {
                    dp[i][j] = dp[i-1][j];
                    from[i][j] = j;
                }
                else
                {
                    if(dp[i-1][j] > dp[i][j-cost[i-1]]+1)
                    {
                        dp[i][j] = dp[i-1][j];
                        from[i][j] = j;
                    }
                    else    //相等的时候也应该选择从当前的这一位转移过来，因为高位越多数字越大
                    {
                        dp[i][j] = dp[i][j-cost[i-1]] + 1;
                        from[i][j] = j - cost[i-1];
                    }
                }
            }
        }
        if(dp[9][target] <= 0) return "0";
        string ans = "";
        int i = 9, j = target;
        while(i>0)
        {
            if(from[i][j] == j) i--;
            else
            {
                ans += (char)('0' + i);
                j = from[i][j];
            }
        }
        return ans;
    }
};

class Solution {
public:
    string largestNumber(vector<int> &cost, int target) {
        vector<int> dp(target + 1, INT_MIN);
        dp[0] = 0;
        for (int c : cost) {
            for (int j = c; j <= target; ++j) {
                dp[j] = max(dp[j], dp[j - c] + 1);
            }
        }
        if (dp[target] < 0) {
            return "0";
        }
        string ans;
        for (int i = 8, j = target; i >= 0; i--) {
            for (int c = cost[i]; j >= c && dp[j] == dp[j - c] + 1; j -= c) {
                ans += '1' + i;
            }
        }
        return ans;
    }
};