题意：

有数码 各无限个，消耗一个数码 需要的代价为 ，现有大小为 的可消耗代价，问可以凑成的最大数字为多少？

解法一（完全背包）：

注意到每个数码可以用一次和多次，使用数码需要消耗一定的代价，这显然是一个变形的完全背包问题。
现在需要解决的是，有一个数字字符串 ，要将数码 插入到数字字符串 中，怎样可以让结果最大？
我们记使得结果最大的数字字符串为 。
我们知道，在长度相同的情况下，高位的数码越大可以使得整个数字字符串越大，那么我们容易设计出如下算法：

从高位到低位遍历数字字符串 ，若数码 大于等于当前遍历到的数码，则将数码 插入到当前位置。

若我们要将数码插入到数字字符串中，

class Solution {
public:
    string buyNumber(int n, vector<int>& a) {
        string* f=new string[n+1];// 动态申请内存
        for(int i=1;i<=9;i++){//数码1~9
            for(int j=a[i-1];j<=n;j++){//背包容量为j
                string t=f[j-a[i-1]];
                int k=0;//k为插入位置
                for(;k<t.size();k++){
                    if(i>=t[k]-'0')break;
                }
                if(k==t.size()){//插到末尾
                    t.push_back(i+'0');
                    //数字字符串比较大小
                    if(t.size()>f[j].size()||(t.size()==f[j].size()&&t>f[j])){
                        f[j]=t;
                    }
                }else{//插到中间
                    string x=t.substr(0,k);
                    x.push_back(i+'0');
                    x+=t.substr(k,t.size()-k);
                    //数字字符串比较大小
                    if(x.size()>f[j].size()||(x.size()==f[j].size()&&x>f[j])){
                        f[j]=x;
                    }
                }
            }
        }
        if(f[n].size()==0)return "-1";
        return f[n];
    }
};

时间复杂度： ，状态转移外面两层循环是 的，最内部的循环复杂度与字符串长度有关， 最坏情况字符串长度为 ，即 ，故总的时间复杂度为
空间复杂度： ，字符串数组长度是 的，根据上述，最坏情况字符串长度为 ，故总的空间复杂度为

解法二（贪心）：

显然，有如下两点结论：

1. 数字字符串位数越多，所表示的数字越大
2. 在数字字符串位数相同的情况下，越高位的数字越大，所表示的数字越大

那么，我们可以首先求出已有的费用 最多可以表示的数位位数。
然后我们可以尝试从高位到低位，从大数码到小数码替换掉当前数字字符串中的数位。
代码：

class Solution {
public:
    string buyNumber(int n, vector<int>& a) {
        int t=1;//t为使得数字字符串数位最多的数码
        for(int i=2;i<=9;i++){
            if(n/a[i-1]>n/a[t-1]){
                t=i;
            }
        }
        string ans(n/a[t-1],t);//初始化数字字符串的数码全部为t
        for(int i=0,sz=n/a[t-1];i<sz;i++){
            n-=a[t-1];//记录消耗的费用
        }
        int idx=8;//从数码9开始（这边对应a中的下标为8）
        for(int i=0;i<ans.size();i++){
            while(idx+1>ans[i]&&n+a[ans[i]-1]<a[idx]){
//替换掉的数码一定要大于当前数码，否则没有意义，并且剩余的费用+退还数码的费用需要能够买下当前数码
                idx--;
            }
            if(idx+1>ans[i]){
                n=n+a[ans[i]-1]-a[idx];
                ans[i]=idx+1;
            }else{
                break;
            }
        }
        if(ans.size()==0)return "-1";
        for(int i=0;i<ans.size();i++){
            ans[i]+='0';
        }
        return ans;
    }
};

时间复杂度： ，主循环过程中，实际上是利用总费用不断地购买数码，因此 实际上是不断减小的，每次购买的代价为 ，故总的时间复杂度为
空间复杂度： ，这边空间复杂度依赖于答案字符串的长度，数位最多为 ，故空间复杂度为