8-1 ナップサック問題

問題

ALGORITHM NOTE ナップザック問題 Knapsack Problem

5つの荷物（重量と価値はそれぞれ、（3と4）（4と5）（5と6）（6と7）（9と10） が各1個）がある。
重量の合計が15以内で、最も価値の合計が高くなるような荷物の組合せを見つけよ。

荷物名  重量  価値
------  ----  ----
A       3      4
B       4      5
C       5      6
D       6      7
E       9     10

ソース

#include <iostream>
#include <Windows.h>
#include <string>
#include <vector>
#include <stack>

struct nimotuDef
{
    std::string Name;
    int Kg;
    int Val;
};

struct JyoutaiDef
{
    int ArrP;
    int SumKg;
    int SumVal;
    std::string Path;
};

void main()
{
    nimotuDef nimotuArr[5];
    nimotuArr[0].Name = "A"; nimotuArr[0].Kg = 3; nimotuArr[0].Val = 4;
    nimotuArr[1].Name = "B"; nimotuArr[1].Kg = 4; nimotuArr[1].Val = 5;
    nimotuArr[2].Name = "C"; nimotuArr[2].Kg = 5; nimotuArr[2].Val = 6;
    nimotuArr[3].Name = "D"; nimotuArr[3].Kg = 6; nimotuArr[3].Val = 7;
    nimotuArr[4].Name = "E"; nimotuArr[4].Kg = 9; nimotuArr[4].Val = 10;

    std::vector<JyoutaiDef> VectJyoutaiDef;
    std::stack<JyoutaiDef> StkJyoutaiDef;

    const int nimotuArrUB = sizeof(nimotuArr)/sizeof(nimotuDef)-1;
    for (int I = 0; I <= nimotuArrUB; I++) {
        JyoutaiDef WillPush;
        WillPush.ArrP = I;
        WillPush.SumKg = nimotuArr[I].Kg;
        WillPush.SumVal = nimotuArr[I].Val;
        WillPush.Path = nimotuArr[I].Name;

        StkJyoutaiDef.push(WillPush);
    }

    while (StkJyoutaiDef.empty() == false) {
        JyoutaiDef Popped = StkJyoutaiDef.top(); StkJyoutaiDef.pop();
        VectJyoutaiDef.push_back(Popped);

        for (int I = Popped.ArrP+1; I <= nimotuArrUB; I++) {
            JyoutaiDef WillPush;
            WillPush.ArrP = I;
            WillPush.SumKg = Popped.SumKg + nimotuArr[I].Kg;
            WillPush.SumVal = Popped.SumVal + nimotuArr[I].Val;
            WillPush.Path = Popped.Path + nimotuArr[I].Name;

            if (WillPush.SumKg <= 15) StkJyoutaiDef.push(WillPush);
        }
    }

    int MaxSumVal = 0;
    for(std::vector<JyoutaiDef>::iterator it = VectJyoutaiDef.begin();it!= VectJyoutaiDef.end();it++){
        if (MaxSumVal < (*it).SumVal) MaxSumVal = (*it).SumVal;
    }
    for(std::vector<JyoutaiDef>::iterator it = VectJyoutaiDef.begin();it!= VectJyoutaiDef.end();it++){
        if ((*it).SumVal == MaxSumVal)
            printf("SumKg=%d,SumVal=%d,Path=%s\n",(*it).SumKg,(*it).SumVal,(*it).Path.c_str());
    }
}

実行結果

SumKg=15,SumVal=18,Path=BCD

解説

重量の合計が15以内の全組み合わせをvectorコンテナに列挙してます。