问给定一串数组A, 每个数字选或者不选, 问是否能凑成tar值, 并返回选择的数字
复杂度
不好估计
如果部分元素重复, 假设重复的个数为cnt, 去重后的数字个数为m, 复杂度就是 O(m*log(cnt)*tar)
如果所有元素都不一样, 那么复杂度就会退化成 O(n*tar)
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
31
32
33
34
35
36
37
38
39
40
| // in: vector<val, cnt>
map<int, int> dpFn(vector<pair<int, int> > &in, int tar) {
vector<bool> dp(tar + 1);
vector<pair<int, int> > path(tar + 1);
dp[0] = 1;
path[0] = {0, 0};
// in数组表示 array<x,y> x是物品价值, y是该物品最多能取y次
// tar表示价值为tar
// dp表示是否能取到价值为dp[i]
// path表示第一次取到该价值时候的物品id和数量 <id,y> 物品价值就是 in[id].first
// 然后每次减去 价值*数量, 得出一条获取物品的路线
for (int idx = 0; idx < in.size(); idx++) {
auto &[val, num] = in[idx];
for (int k = tar; k >= 0; k--) {
if (dp[k]) {
for (int cnt = 1; num; cnt<<=1) {
int c = min(num,cnt);
num -= c;
if (k + c * val <= tar && dp[k + c * val] == 0) {
dp[k + c * val] = 1;
path[k + c * val] = {idx, c};
}
}
}
}
}
map<int, int> ans;
int cur = tar;
// 逆推出路线 每次减去 in[id].first * num
while (cur) {
auto [id, num] = path[cur];
cur -= num * in[id].first;
ans[in[id].first] = num;
}
return ans;
}
|