题目描述

给你一个整数数组 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" 的代价为 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

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

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

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

提示：

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

算法分析

完全背包求具体方案 + 贪心

每个数字的价值是1，尽可能选更多的数，这样组成的数字会越大，并且价值相同时，前面的位置尽可能选数字最大的

状态表示

• f[i,j]表示从前i个中选，且总体积恰好是j的最大价值

状态计算

• f[i,j] = Math.max(f[i - 1,j],f[i,j - w[i]] + 1)

算出最大价值f[9,target]，逆向找出对应的具体方案，通过贪心原则，若当前数字i可以选就一定选，得出来的结果一定是最优，从f[9,target]开始，若当前状态是f[i,j]，若f[i,j]= f[i,j - w[i]] + 1，则表示f[i,j]可以从f[i,j - w[i]] 转移过来，并且可以选上i这个数字

时间复杂度 $O(n * target)$

Java 代码

class Solution {
    public String largestNumber(int[] cost, int target) {
        int n = 9;
        int[][] f = new int[10][5010];
        int[] w = new int[10];
        Arrays.fill(f[0],-0x3f3f3f3f);
        for(int i = 1;i <= n;i ++) w[i] = cost[i - 1];

        for(int i = 1;i <= n ;i ++)
        {
            for(int j = 1;j <= target;j ++)
            {
                f[i][j] = f[i - 1][j];
                if(j >= w[i])
                    f[i][j] = Math.max(f[i][j], f[i][j - w[i]] + 1);  
            }
        }

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

        String ans = "";
        for(int i = 9,j = target;i >= 1;i --)
        {
            while(j >= w[i] && f[i][j] == f[i][j - w[i]] + 1)
            {
                ans += i;
                j -= w[i];
            }
        }
        return ans;
    }
}