C++でナップサック問題を解く方法

2年 ago
蓮, 翼
1 minute

C++では、 배낭 문제를 해결하는 데 배열이나 연결 리스트를 사용할 수 있습니다.

まず、重量や価値などの情報を含むアイテムを表す構造体またはクラスを定義します。

次に、ナップサックの容量と、現在ナップサックに入っているアイテムを表す配列やリンクリストを定義します。

続けて、動的計画法の考え方を用いて、ナップサック問題を解くことができる。ここで、2 次元配列 dp を定義し、dp[i][j] は、最初の i 個の品物で、ナップサックの容量が j のときの最大の価値を表す。

最初のアイテムから順に見ていき、各アイテムでバックパックに入れるか入れないかを考えます。

リュックサックに入れる場合、dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1]、ここでw[i-1]はi番目のアイテムの重さを表し、v[i-1]はi番目のアイテムの価値を表す。

バッグに入れない場合、dp[i][j] = dp[i-1][j]

dp[i][j] の値を、以上の 2 つのケースの最大値とする。

結論として、ナップサック問題の解は dp[n][c] となり、n はアイテムの数、c はナップサックの容量を表します。

以下に、配列を使用して実装された C++ コードの例を示します。

#include <iostream>
#include <vector>
using namespace std;

struct Item {
    int weight;
    int value;
};

int knapsack(vector<Item>& items, int capacity) {
    int n = items.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (items[i - 1].weight <= j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i - 1].weight] + items[i - 1].value);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][capacity];
}

int main() {
    vector<Item> items{{2, 3}, {3, 4}, {4, 5}, {5, 6}};
    int capacity = 8;
    int max_value = knapsack(items, capacity);
    cout << "The maximum value is: " << max_value << endl;
    return 0;
}

この例では、アイテムの重さや価値は配列itemsで表され、ナップサックの容量は変数capacityで表されています。ナップサック問題は関数knapsackで解決され、ナップサック中で得られる最大の価値を返します。

そのコードを実行すると、結果は次のようになります。

The maximum value is: 9
bannerAds