1

この問題の簡単な dp ソリューションがあります。

#include <vector>
#include <limits>

int knapsack2(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
    size_t n = wts.size();
    std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n+1, 0));
    for (size_t j = 1; j <= n; j++) {
        for (int w = 1; w <= W; w++) {
           if (wts[j-1] <= w) {
               dp[w][j] = std::max(dp[w][j - 1], dp[w - wts[j-1]][j - 1] + cost[j-1]);
           }
           else {
                dp[w][j] = dp[w][j - 1];
           }
        }
    }
    return dp[W][n];
}

しかし、どのオブジェクトが取得されたかをどのように知ることができますか?

4

3 に答える 3

0

マップを使用できます。オブジェクトが作成されると、マップを使用してクエリを作成できるようになります。最適化アルゴリズムは、HashMap を使用して実現されます。

于 2013-01-31T08:51:15.603 に答える
0

あなたのアプローチの主な問題は、アイテムの概念をエンティティとしてエンコードしていないことです。メンバーとして重量、コスト、およびある種の識別子 (名前または番号) を持つアイテムを記述するには、(classまたはキーワードを使用して) タイプ「アイテム」を作成する必要があります。structそうすれば、アイテムの単一のベクトルを送信するだけで済み、ソリューションはそのようなアイテムのリストになり、質問に答えます。

編集

リクエストに応じて、これを単純に機能させる方法のより実用的な説明を以下に示します。

item1 つのアイテムのすべての情報を含むタイプを作成します。を入力として取り、とのstd::vector<item>両方を置き換えます。最小の変更は、ランニング コストとアイテム リストのペアを格納するように変更することです。これにより、 type が与えられます。つまり、保存された (部分的な) ソリューションごとに、そのコストとこのソリューションを提供するアイテムを追跡します。wtscostdpstd::vector<std::vector<std::pair<int,std::vector<item>>>>

このタイプの fordpはかなりおぞましいものに見えますが、うまく機能するようになれば、後で実装を改善できます。たとえば、itemコピーを回避するために、s へのポインターを格納できます。また、いくつかtypedefの s は . の定義を明確にするのに本当に役立ちdpます。重要なことは、最初に最も単純なソリューションで動作するようにし、次にそれらの改善について考えることです。

于 2013-01-31T08:47:07.860 に答える
0

dp と同じ次元の 2 番目のベクトル「prev」を作成します。

dp[w][j] に最適なオプションを選択すると、前のセルの座標が prev[w][j] に書き込まれます

dp のジョブが完了したら、prev[W][n] から戻って、使用されているすべてのセル インデックスを取得します。

于 2013-01-31T12:52:39.607 に答える