c++ 完全背包一维

class Solution {
public:
    string largestNumber(vector<int>& cost, int t) {
        int f[t+5];
        memset(f, 0xcf, sizeof f);
        f[0] = 0;

        for (int i = 1; i <= 9; ++i) {
            for (int j = 1; j <= t; ++j) {
                int c = cost[i - 1];
                if (j >= c) {
                    f[j] = max(f[j], f[j - c] + 1);
                }
            }
        }
        if (f[t] < 0) {
            return "0";
        } else {
            string res = "";
            while (t) {
                for (int i = 9; i >= 1; i--) {
                    int c = cost[i - 1];
                    if (t >= c && f[t] == f[t- c] + 1) {
                        res += to_string(i);
                        t -= c;
                        break;
                    }
                }
            }
            return res;
        }
    }
};