考点
思路
完全背包的精髓题，必刷
我先证明一下完全背包的转移本质，数学上的严谨推导
完全背包
要得到最大数字，要保证位数尽可能大；若位数相同，保证字典序大
先用完全背包先求出
f[t] = 凑出总价 t 的最大位数，转移（允许无限用某个数字
i）：
1
2
| f[0] = 0
f[t] = max( f[t - cost[i]] + 1 ) （t ≥ cost[i]）
|
不可达记为 -INF
复原答案时，逆向考虑DP，并从高位到低位、从 9 到 1
尝试放数字 i： 只要 t >= cost[i] 且
f[t] == f[t - cost[i]] + 1，就说明放一枚
i不会降低“最大位数”，于是就放它，并令
t -= cost[i]；继续尝试同一个
i（因为是完全背包）。
这样得到的字符串必定数值最大：先保证位数最优，再尽可能让高位用更大的数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
string largestNumber(vector<int>& cost, int target) {
int f[10][5005];
memset(f, 0xcf, sizeof(f));
f[0][0] = 0;
int n = cost.size();
for (int i = 1; i <= n; ++i) {
int x = cost[i - 1];
for (int j = 0; j <= target; ++j) {
if (f[i - 1][j] >= 0) f[i][j] = max(f[i][j], f[i - 1][j]);
if (j >= x && f[i][j - x] >= 0) f[i][j] = max(f[i][j], f[i][j - x] + 1);
}
}
if (f[n][target] < 0) return "0";
int t = target;
string ans;
for (int i = 9; i >= 1 && t; --i) {
int x = cost[i - 1];
while (t >= x && f[i][t - x] + 1 == f[i][t]) {
ans += (char)(i + '0');
t -= x;
}
}
return ans;
}
};
|
递推
由于数据范围小，可以直接用递推暴力枚举，省下一维
需要重复一遍，大多数情况下的DP逆向是不可以压缩的，因为这样会覆盖历史情况
这里递推的式子长得很像上面的完全背包压缩后的情况，但完全不是一个东西，所以可以用一维
定义：
1
| f[t] = 在可以使用数字 1..9（不限次数）时，凑出总代价 t 的最大位数
|
递推是数学上直接定义出来的： \[
f[t] = \max_{d=1..9,\ t \ge cost[d]} \{ f[t - cost[d]] + 1 \},
\quad f[0]=0
\] 得到一维的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
string largestNumber(vector<int>& cost, int target) {
int f[5005];
memset(f, 0xcf, sizeof(f));
f[0] = 0;
for (int i = 1; i <= target; ++i) {
for (int j = 1; j <= 9; ++j) {
if (i >= cost[j - 1] && f[i - cost[j - 1]] != 0xcfcfcfcf)
f[i] = max(f[i], f[i - cost[j - 1]] + 1);
}
}
if (f[target] == 0xcfcfcfcf) return "0";
int t = target;
string ans;
for (int i = 9; i >= 1 && t; --i) {
int x = cost[i - 1];
while (t >= x && f[t - x] + 1 == f[t]) {
ans += (char)(i + '0');
t -= x;
}
}
return ans;
}
};
|