圣诞礼物｜完全背包问题变型

第六题 - A23471.圣诞礼物

题目链接跳转：A23471.圣诞礼物

一道很明显的完全背包问题，但需要加以优化。如果不优化的话，按照本题的数据量，在极端情况下程序会运行 $10^5 \times 10^5 = 10^{10}$ 次，大概需要 $2$ 分钟时间（其实也不是很久）。因此我们需要在原本的完全背包的基础上加以优化：

通过观察可以发现，虽然物品的数量有 $10^5$ 种，但是每种物品的花销却极其的少。就算有一个幸运数字为 $888888888$，那么也只需要 $63$ 个圣诞糖果就可以。假设有多个幸运数字都需要 $10$ 个糖果，那按照贪心的思路：如果我们要选支出则 $63$ 个圣诞糖果的话，我们可以获得的最大收益就是所有需要 $10$ 个糖果的幸运数字所对应的可以获得的金币数量的最大值。我们可以通过一个数组来记录对于每一种支付的糖果组合，可以获得的最大金币数量。

这样子我们就将原本的物品数量成功压缩成了 $63$ 种物品，即可通过本题的所有测试点。本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;

const int N = 1e5 + 5;
const int K = 500;
int T, n, m;
int A[N], B[N], C[K], vis[K], dp[N];
int nums[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int calc(int num){
    int total = 0;
    while(num){
        total += nums[num % 10];
        num /= 10;
    }
    return total;
}

void solve(){
    cin >> n >> m;
    for (int i=1; i<=n; i++) cin >> A[i];
    for (int i=1; i<=n; i++) cin >> B[i];
    // 每次记得都要初始化（否则大祸临头）。
    for (int i=1; i<=m; i++) dp[i] = 0;
    for (int i=1; i<=100; i++) C[i] = vis[i] = 0;
    for (int i=1; i<=n; i++){
        int t = calc(A[i]);
        vis[t] = 1;
        // 贪心取最优的。
        C[t] = max(C[t], B[i]);
    }
    int ans = 0;
    for (int i=1; i<=105; i++){
        if (vis[i] == 0) continue;
        for (int j=i; j<=m; j++){
            dp[j] = max(dp[j], dp[j-i] + C[i]);
        }
    }
    cout << dp[m] << endl;
    return ;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> T; while(T--) solve();
    return 0;
}

本题的 Python 代码如下：

T = int(input())

nums = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def calc(num):
	ans = 0
	while num:
		ans += nums[num % 10]
		num //= 10
	return ans

while T:
	T -= 1
	n, m = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C, vis = [0 for _ in range(105)], [0 for _ in range(105)]
	dp = [0 for _ in range(m+1)]
	for i in range(0, n):
		t = calc(A[i])
		vis[t] = 1
		C[t] = max(C[t], B[i])
	ans = 0
	for i in range(1, 105):
		if vis[i] != 1:
			continue
		for j in range(i, m+1):
			dp[j] = max(dp[j], dp[j-i] + C[i])
	print(dp[m])

本题的每个测试点有多个测试用例，对于每一个测试用例，本算法时间的多项式时间复杂度约为 $O(63M)$，经过化简后的复杂度约为 $O(M)$。其中，数字 $63$ 代表最多存在 $63$ 中不同的“物品”。