C++01リュックサック動的計画を実現し、選択したものを出力する

本文は参考にして調べる:動的計画の01リュック問題(最も理解しやすい説明)アルゴリズム設計と分析–01リュック問題(動的計画法解決)
01バックパックの再帰や動的計画の再帰や動的計画サイクルについてはネット上にたくさんありますが、コードが乱れていると思いますので、自分で記録することにしました.ここでは動的計画サイクルの実現方法だけを記録します.
借用テーブル(上の最初のリンクからソース)
(下から上、左から右)
状態遷移方程式(上図より):
式＃シキ＃
条件
dp[i][j] = dp[i + 1][j]
j < Wi
dp[i][j] = max(dp[i + 1][j] , dp[i + 1][j - Wi] + Vi)
j >= Wi
注記:dp[i][j]の値は、iから最後の物品の最大荷重jでの最大価値、Wi:物品iの重量、Vi:物品iの価値である.
直接コード:

#include 
#include 
#include 

using namespace std;

//     ,  ,  ,     
struct Item
{
    int Wi = 0;
    int Vi = 0;
    bool selected = false;
};

//       ,           
vector vecItem;

int dp[200][5001];

//    ,      
int getMaxValue(int itemsSize, int maxWeight);

//           
void findSelectedItems(int itemsSize, int maxWeight);

int main()
{
    int n, maxW;
    //     ,    
    cin >> n >> maxW;
    for (size_t i = 0; i < n; ++i)
    {
        Item item;
        cin >> item.Wi >> item.Vi;
        //      ,             ,            vecItem.size()   n .
        if (item.Wi <= maxW)
            vecItem.push_back(item);
    }

    //      
    maxValue = getMaxValue(vecItem.size(), maxW);

    //            ,         
    findSelectedItems(vecItem.size(), maxW);

    cout << "max value :" << maxValue <"selected items :"<for (size_t i = 0; i < vecItem.size(); ++i)
    {
        if (vecItem[i].selected)
            cout <<"index "<< i << " : "<< vecItem[i].Wi << " - " << vecItem[i].Vi << endl;
    }

    system("pause");
    return 0;
}

コアダイナミックプランニング

int getMaxValue(int itemsSize, int maxWeight)
{
    //    ,     
    for (int j = 1; j <= maxWeight; ++j)
    {
        //          ,            ,        ,             ,        
        if (vecItem[itemsSize - 1].Wi <= j)
            dp[itemsSize - 1][j] = vecItem[itemsSize - 1].Vi;
        for (int i = itemsSize - 2; i >= 0; --i)
        {
            //           
            if (j < vecItem[i].Wi)
                dp[i][j] = dp[i + 1][j];
            else
                dp[i][j] = max(dp[i + 1][j - vecItem[i].Wi] + vecItem[i].Vi, dp[i + 1][j]);
        }
    }
    return dp[0][maxWeight];
}

選択したアイテムを押し出す

void findSelectedItems(int itemsSize, int maxWeight)
{
    // dp     ,    ,      ,i         
    int k = maxWeight;
    for (int i = 0; i < itemsSize; ++i)
    {
        if (dp[i][k]>dp[i + 1][k])
        {
            vecItem[i].selected = true;
            k -= vecItem[i].Wi;
        }
    }
}

この例に従って実行結果:
dp配列の内容を見ると、上のカラーマップと同じです(vsコンパイラは本当に666で、爆発に使います)