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

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

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

样例1

解释:总成本是 target 的条件下,无法生成任何整数。

首先,要求得到最大整数,因此要拼出一个数位越长越好,高位的数字越大越好的一个数。

把9个数字看作9个物品;每个数字的花费看作体积;其中target视为目标体积:这是完全背包的模型 直白点就是从9个物品中选且体积恰好为target的所有方案。

由于这里没有说每个数是多少价值 价值可以默认为1:那么 f(ij)就表示从前i个物品中选,且体积恰好为j的最大价值。放到题目上的意思就是:f(ij)表示从前i个数字中选,且花费恰好为j的最大位数;

求出所有方案之后,接下来是背包问题求具体方案或者说从f(ij)所表示的集合中找出一组特定方案。数字尽可能要大,高位应该从数字9开始往回拼,就能找到答案。

完全背包的时间复杂度不太清楚是不是这样算 有知道的告诉我hh