1

次の問題に取り組んでいます: n 個のアイテムのセットが与えられた場合、厳密に小さく、指定された数 m にできるだけ近いサイズ k のサブセットの最大合計を見つけます。

サブセットのサイズが 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