アルゴリズムノート(c++)--完全なリュックサックの問題

アルゴリズムノート(c++)--完全リュックと多重リュックの問題
完全リュックサック
完全なリュックサックは01リュックサックとは異なります.完全なリュックサックの中のものの数は無限です.
現在5つのアイテムの重量が5,4,3,2,1であると仮定します.
価値は1,2,3,4,5
バックパック容量は10

#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;
}

 
その他はすべて01リュックと同じで、jを巡るときの初期化が違います.
ここでのdp[j]は,j容量のリュックサックを前のi品に入れることで得られる最大の価値を表し,更新するたびに必ず現在の最適解であることを保証する.最長増分子シーケンスを求めるように.すべての状況を一度経験して最大の結果を得たのです.
あまり話さずに直接数歩推定すれば全部わかる.
1)まず,物品1号のみの場合,jを1号物品の重量5に初期化する.
dp[5]=max(dp[5],dp[5-5]+1]=1
dp[6]からdp[9]までが1であり、dp[10]=2
2)そして現在は物品1号と2号があり,jは2号の物品重量4に初期化されている.
dp[4]=max(dp[4],dp[4-4]+2)=2
dp[5]=max(dp[5],dp[5-4]+2)=2
dp[..8]=max(dp[8],dp[8-4]+2)=4
実はここまでも差は少なく、下は同じです.
私たちはこの品物を入れるかどうかを決めて、この品物の大きさからリュックサックの容量を遍歴して、それから毎回遍歴して、もし今この品物の空間を空けて元の価値よりも大きいならば、入れます.
違い---------01リュックと完全リュック
01リュックサックの遍歴は逆で、更新は前に影響しません.
完全なリュックサックが遍歴しているので、前のものが変わるので、何度も保管されています.
 
多重リュックサック
多重リュックサックはもう少し制限があり、数に制限があります.
データは次のとおりです.
数量
じゅうりょう
価値
0
0
0
1
5
1
2
4
2
1
3
3
2
2
4
1
1
5
 
 
 
 
同じリュックサックを10サイズにします
コードは次のとおりです.

#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;
}

 
今度は一歩一歩来ないで、01を知っていればいいです.
毎回01は1つで完全リュックが複数入っているので、私たちも完全リュックがいくつ入っているか分かりません.だから多重リュックサックは01リュックサックの変種だ.
私たちが遍歴するたびにこの品物を置くかどうか判断している以上、私たちはいっそ何人かを遍歴します.もう1度外を回ってforを追加すればいい
よく分かります.
 
転載先:https://www.cnblogs.com/DJC-BLOG/p/9418438.html