貌似DP的小问题 玄关

学术版

JimmyDong @ 2024-08-10 12:52:44

已知有 k 个集合,分别为 s_1,s_2,...,s_k。

s_1= \{a[1][1],a[1][2],....,a[1][size(s_1)]\} s_2= \{a[2][1],a[2][2],....,a[2][size(s_2)]\}

......

s_k= \{a[k][1],a[k][2],....,a[k][size(s_k)]\}

从每个集合最多选一个数，问在总和不超过 n 的情况下最大是多少。

size(s_i)\leq 5000,k\leq 5000

貌似是 DP

by bcbgszyzh @ 2024-08-10 13:01:22

稍等 @JimmyDong

by JimmyDong @ 2024-08-10 13:01:44

@bcbgszyzh 好

by bcbgszyzh @ 2024-08-10 13:02:16

@JimmyDong 想到了

by bcbgszyzh @ 2024-08-10 13:03:09

@JimmyDong 可以看作多维背包

转移方程为：

dp[j]=max(dp[j],dp[j−a[i][l]]+a[i][l])\ \ \ \ if j≥a[i][l]

by JimmyDong @ 2024-08-10 13:06:12

@bcbgszyzh 可以，关注了

by bcbgszyzh @ 2024-08-10 13:08:22

ok bye @JimmyDong

by bcbgszyzh @ 2024-08-10 13:09:51

@JimmyDong

伪代码：

dp = [0] * (n + 1)

for i in range(1, k + 1):
    for j in range(n, 0, -1):
        for l in range(1, size(s_i) + 1):
            if j >= a[i][l]:
                dp[j] = max(dp[j], dp[j - a[i][l]] + a[i][l])

result = dp[n]

by JimmyDong @ 2024-08-10 13:11:02

@bcbgszyzh

有两个问题： 1.dp表示啥

2.那个 a[i][l]的l是什么

by bcbgszyzh @ 2024-08-10 13:11:56

@yx666

by JimmyDong @ 2024-08-10 13:12:57

@bcbgszyzh 我们就是说这么循环会不会超时捏

| 下一页