ナップザック問題

動的計画法を用いる機会が無くてナップザック問題すら解いたことが無いのでナップザック問題を解きました。

入力

n
w
w1 v1
...
wn vn

n 種類の荷物から自由に選択し、重さ w 以下で価値が最大となる組み合わせを選択する。 i 番目の荷物の重さは wi で価値は vi とする。

n+1 行 w+1 列の 2 次元配列 dp を用意し、 dp[i][j] に「 i 番目までの荷物の中で重さ j 以下となる選択の中での価値の最大値」とすると、 dp[i-1][j] と dp[i-1][j-wi] の中で大きい値を dp[i][j] に代入する繰り返しで dp[n][w] に求める値を代入することが出来ます。前者は「 i 番目の荷物を選ばない場合」、後者は「 i 番目の荷物を選ぶ場合」に相当します。
配列のインデクス j-wi が 0 以上かどうかも検査します。
繰り返しは i=0 または j=0 の場合は 0 に初期化するため飛ばします。

#include <iostream>
#include <vector>
#include <map>

int main(){
    int n;
    int w;
    int **dp;
    std::vector<std::pair<int, int> > xs;

    std::cin >> n;
    std::cin >> w;

    for(int i = 0; i < n; i++){
        int a, b;
        std::cin >> a >> b;
        xs.push_back(std::pair<int, int>(a, b));
    }

    dp = new int*[n + 1];

    for(int i = 0; i < n + 1; i++){
        dp[i] = new int[w + 1];
        for(int j = 0; j < w + 1; j++){
            dp[i][j] = 0;
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= w; j++){
            std::pair<int, int>& p = xs[i - 1];
            int a = dp[i - 1][j];
            int b;

            if(j - p.first >= 0){
                b = dp[i - 1][j - p.first] + p.second;
            }else{
                b = 0;
            }

            dp[i][j] = std::max(a, b);
        }
    }

    std::cout << dp[n][w] << std::endl;

    for(int i = 0; i < n + 1; i++){
        delete [] dp[i];
    }
    delete [] dp;

    return 0;
}

入力例

4
5
2 3
1 2
3 4
2 2

出力例

7

最大値だけではあまり実用性の無いプログラムなので、どのように荷物を選択するか番号を出力するプログラムに変更します。 DP をする際に、どこから遷移してきたのかを保存しておきます。下記のプログラムでは、 遷移前の i,j の組を vector を使って保存しています。 vector にする理由は、荷物の選択方法が複数ある場合を考慮してのことです。 dp[i][0] の遷移前の情報が必要となる為、ループには j=0 の場合も含めます。関数 f で再帰をしながら選択された荷物を確認しています。（ i 番目の荷物が選択されていた場合、遷移前の j の値が異なることを利用する。）

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>

struct Cell{
    int value;
    std::vector<std::pair<int,int> > pred;

    Cell(){
        this->value = 0;
    }
};

void f(Cell **dp, int i, int j, std::vector<int> &xs){
    if(i == 0){
        for(int a = 0; a < xs.size(); a++){
            std::cout << xs[a] << ' ';
        }
        std::cout << std::endl;
    }else{
        for(int a = 0; a < dp[i][j].pred.size(); a++){
            std::pair<int,int> &p = dp[i][j].pred[a];
            if(p.second != j){
                xs.push_back(i);
                f(dp, p.first, p.second, xs);
                xs.pop_back();
            }else{
                f(dp, p.first, p.second, xs);
            }
        }
    }
}

int main(){
    int n;
    int w;
    Cell **dp;
    std::vector<std::pair<int,int> > xs;

    std::cin >> n;
    std::cin >> w;

    for(int i = 0; i < n; i++){
        int a, b;
        std::cin >> a >> b;
        xs.push_back(std::pair<int,int>(a, b));
    }

    dp = new Cell*[n + 1];

    for(int i = 0; i < n + 1; i++){
        dp[i] = new Cell[w + 1];
    }

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= w; j++){
            std::pair<int,int>& p = xs[i - 1];
            int a = dp[i - 1][j].value;
            int b;

            if(j - p.first >= 0){
                b = dp[i - 1][j - p.first].value + p.second;
            }else{
                b = -1;
            }

            if(a > b){
                dp[i][j].value = a;
                dp[i][j].pred.push_back(std::pair<int,int>(i - 1, j));
            }else if(a < b){
                dp[i][j].value = b;
                dp[i][j].pred.push_back(std::pair<int,int>(i - 1, j - p.first));
            }else{
                dp[i][j].value = a;
                dp[i][j].pred.push_back(std::pair<int,int>(i - 1, j));
                dp[i][j].pred.push_back(std::pair<int,int>(i - 1, j - p.first));
            }
        }
    }

    std::cout << dp[n][w].value << std::endl;
    std::vector<int> v;
    f(dp, n, w, v);

    for(int i = 0; i < n + 1; i++){
        delete [] dp[i];
    }
    delete [] dp;

    return 0;
}

入力例1

4
5
2 3
1 2
3 4
2 2

出力例1

7
3 1 
4 2 1 

入力例2

6
5
1 2
1 3
2 5
3 6
4 7
5 8

出力例2

11
4 2 1 
4 3