1

我正在努力解决以下问题：给定一组 n 个项目，找到大小为 k 的子集的最大总和，该子集严格低于并尽可能接近给定数 m。

我已经解决了这个问题，没有子集的大小必须为 k 的约束，这是我的代码（nums 是我保存我的 n 个数字的数组）：

// clear the dp array
int dp[n+1][m+1];
for(int i = 0; i < n+1; i++)
    for(int j = 0; j < m+1; j++)
        dp[i][j] = 0;

for(int j = 1; j <= n; j++)
{
    for(int w = 1; w < m; w++)
    {
        if(nums[j-1] <= w) dp[j][w] = max(dp[j-1][w], nums[j-1] + dp[j-1][w - nums[j-1]]);
        else dp[j][w] = dp[j-1][w];
    }
}
cout << dp[n][m-1];

但是，我不确定如何扩展我的代码以使用大小为 k 的子集给出答案。我正在考虑在表格中使用另一个维度来跟踪已添加的项目，但我不确定如何实现这一点。我已经搜索过这个站点，但没有找到可以帮助我编写代码的具体答案。

谁能帮我解决这个问题？

提前致谢！

4

0 回答 0