01リュック、完全リュック、多重リュックの問題のC++実現

01リュックサックの問題
容量10のリュックサックは、5種類のアイテムがあり、それぞれ1つのアイテムしかなく、その重量はそれぞれ5,4,3,2,1であり、その価値はそれぞれ1,2,3,4,5である.アルゴリズムを設計し、リュックサック内の物品の価値を最大にする.コードは以下の通り(出力14)

#include 
#include

using namespace std;

int main() 
{
    int total_weight = 10;
    int w[6] = { 0,5,4,3,2,1};
    int v[6] = { 0,1,2,3,4,5};
    int dp[11] = { 0 };

    for (int i = 1; i <= 5; i++)
        for (int j = 10; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << "     : " << dp[10] << endl;
    return 0;
}

完全なリュックサック問題
容量10のリュックサックは、5種類のアイテムがあり、それぞれのアイテムの数は無限で、その重量はそれぞれ5、4、3、2、1で、その価値はそれぞれ1、2、3、4、5です.アルゴリズムを設計し、リュックサック内の物品の価値を最大にする.コードは以下の通り(出力50)

#include 
#include

using namespace std;

int main() 
{
    int total_weight = 10;
    int w[6] = { 0,5,4,3,2,1};
    int v[6] = { 0,1,2,3,4,5};
    int dp[11] = { 0 };

    for (int i = 1; i <= 5; i++)
        for (int j = w[i]; j <= 10;j++)
                dp[j] = max(dp[j],dp[j - w[i]] + v[i]);

    cout << "     : " << dp[10] << endl;
    return 0;
}

多重リュックサック問題
容量10のリュックサックは、5種類のアイテムがあり、それぞれのアイテムの数は1,2,1,2,1であり、その重量はそれぞれ5,4,3,2,1であり、その価値はそれぞれ1,2,3,4,5である.アルゴリズムを設計し、リュックサック内の物品の価値を最大にする.コードは以下の通り(出力16)

#include 
#include

using namespace std;

int main()
{
    int total_weight = 10;
    int w[6] = { 0,5,4,3,2,1 };
    int v[6] = { 0,1,2,3,4,5 };
    int cot[6] = { 0,1,2,1,2,1 };
    int dp[11] = { 0 };

    for (int i = 1; i <= 5; i++)
        for (int k = 1; k <= cot[i];k++)
            for (int j = 10; j >= w[i]; j--)
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << "     : " << dp[10] << endl;
    return 0;
}