背包問題 - jesse

0-1 バックパック#

N 個のアイテムと容量 V のバックパックがあります。i 番目のアイテムを入れるのにかかるコストは cost [i]、価値は value [i] です。どのアイテムをバックパックに入れると価値の合計が最大になるかを求めます。

//初期化
let v = 2;//バックパックの容量
let n = 4;//アイテムの数、cost と value の長さと等しくなければならない
let cost = vec![1, 2, 3, 4];//アイテムのコスト
let value = vec![1, 3, 5, 7];//アイテムの価値
let mut f = vec![0; v + 1];

// 0 <= i < n
for i in 0..n {
    zoro_one_pack(&mut f, cost[i], value[i], v);
}
//最後の価値の合計が最大の値は f[v] です

fn zoro_one_pack(f: &mut Vec<usize>, cost: usize, value: usize, v: usize) {
    for j in (cost..=v).rev() {
        f[j] = std::cmp::max(f[j], f[j - cost] + value);
    }
}

注意：

もし問題が ちょうどバックパックを満たすこと を要求する場合、f[0] を 0 に設定し、残りはすべて $-∞$ に設定します。もし ちょうど満たすこと を要求しない場合、f はすべて 0 に初期化します。

定数の最適化#

//擬似コード
for i in 0..n {
    for j in (cpm::max(cost[i],v-(cost[i]+..+cost[n-1]))..=v).rev() {
        f[j] = std::cmp::max(f[j], f[j - cost[i]] + value[i]);
    }
}

完全バックパック#

N 種類のアイテムと容量 V のバックパックがあります。各アイテムは 無限に 使用可能です。i 番目のアイテムのコストは cost[i]、価値は value[i] です。どのアイテムをバックパックに入れると、これらのアイテムのコストの合計がバックパックの容量を超えず、かつ価値の合計が最大になるかを求めます。

考え方は 0-1 バックパックに変換すること です：1 種類のアイテムを複数のアイテムに分解し、0 個または 1 個しか選べない 01 バックパックのアイテムにします。

//初期化
let v = 2;//バックパックの容量
let n = 4;//アイテムの数、cost と value の長さと等しくなければならない
let cost = vec![1, 2, 3, 4];//アイテムのコスト
let value = vec![1, 3, 5, 7];//アイテムの価値
let mut f = vec![0; v + 1];

// 0 <= i < n
for i in 0..n {
    complete_pack(&mut f, cost[i], value[i], v);
}
//最後の価値の合計が最大の値は f[v] です

fn complete_pack(f: &mut Vec<usize>, cost: usize, value: usize, v: usize) {
    //これは 0-1 バックパックの内側のループの順序を反転させることです
		for j in cost..=v {
        f[j] = std::cmp::max(f[j], f[j - cost] + value);
    }
}

多重バックパック#

N 種類のアイテムと容量 V のバックパックがあります。i 番目のアイテムは最大 M[i] 個使用可能で、各アイテムのコストは cost[i]、価値は value[i] です。どのアイテムをバックパックに入れると、これらのアイテムのコストの合計がバックパックの容量を超えず、かつ価値の合計が最大になるかを求めます。

fn multiple_pack(f: &mut Vec<usize>, cost: usize, value: usize, v: usize, mut m: usize) {
    if cost * m >= v {
        complete_pack(f, cost, value, v);
        return;
    }
    let mut k = 1;
    while k < m {
        zoro_one_pack(f, k * cost, k * value, v);
        m -= k;
        k *= 2;
    }
    zoro_one_pack(f, m * cost, m * value, v)
}

実現可能性の問題#

問題が「各種類のアイテムが与えられた容量のバックパックを満たすことができるか」である場合、バックパックを満たす実現可能性のみを考慮し、各アイテムの価値を考慮する必要はありません。この場合、多重バックパック問題も O (VN) の複雑度のアルゴリズムがあります。

fn multiple_pack_ok() {
		//コインモデルを使って理解することもできます。v はコインの総価値、n はコインの種類、
    //m は各コインの数量、cost は各種類のコインの価値を表します
    let v = 2;
    let n = 4;
    let cost = vec![5, 4, 9, 3];
    let m = vec![2, 1, 4, 6];
    let mut f = vec![-1; v + 1];
    f[0] = 0;

    for i in 0..n {
        for j in 0..=v {
            if f[j] >= 0 {
                f[j] = m[i];
            }
						//else {
            //    f[j] = -1; 初期化はすでに -1 です
            //}
        }
        if v < cost[i] {
            break;
        }
        for j in 0..=(v - cost[i]) {
            if f[j] >= 0 {
                f[j + cost[i]] = std::cmp::max(f[j + cost[i]], f[j] - 1);
            }
        }
    }
}

f[i][j] は前の i 個のアイテムを使用して容量 j のバックパックを満たすことを示し、i 番目のアイテムは最大で何個残っているかを示します。もし容量 j のバックパックを満たすことができない場合、その値は -1 です。

まず、f[i - 1][j] は前の i - 1 件のアイテムで価値 j を作ることを示します。その値が 0 以上であれば、状態は合法であり j を作ることができることを示しますので、次に i 番目のコインを使わずに j を作ることができることになります。したがって、残りのコインの数は m[i] です。
もし f[i - 1][j] が 0 未満であれば、前の i-1 種類では j を作ることができないことを示します。i 番目のコインを加えると、価値が大きすぎるか、ちょうど良いかもしれませんので、まずは -1 を仮定します。
f[i][j + cost[i]] = std::cmp::max(f[i][j + cost[i]], f[i][j] - 1); もし j + cost[i] を作ることができれば、コインの数を -1 します。もしできなければ、-1 の状態を維持します。

その後、2 次元配列を 1 次元配列に変更します。

混合バックパック#

上記の 3 種類のバックパックを混合したものです。

//擬似コード：
for i in 0..n{
	if i は 01 バックパック {
		zero_one_pack(..);
	}else if i は完全バックパック {
		complete_pack(..);
	}else if i は多重バックパック {
		multiple_pack(..);
	}
}

男性八題の多重バックパック問題

2 次元バックパック#

各アイテムには 2 種類の異なるコストがあり、このアイテムを選択するには両方のコストを同時に支払う必要があります。各コストには支払える最大値（バックパックの容量）があります。どのようにアイテムを選択すれば最大の価値を得られるかを問います。

i 番目のアイテムに必要な 2 種類のコストをそれぞれ Ci と Di とします。2 種類のコストの最大値（すなわち 2 種類のバックパックの容量）はそれぞれ V と U です。アイテムの価値は Wi です。

状態遷移方程式は次のようになります：

F[i, v, u] = max{F[i − 1, v, u], F[i − 1, v − Ci, u − Di] +Wi}

時には、「2 次元コスト」の条件がこのような暗黙の方法で与えられることがあります：最大で U 件のアイテムしか取れない。
これは実際には各アイテムに「件数」のコストが追加され、各アイテムの件数コストは 1 であり、支払える最大件数コストは U です。

グループバックパック#

N 件のアイテムと容量 V のバックパックがあります。i 番目のアイテムのコストは Ci、価値は Wi です。これらのアイテムは K グループに分けられ、各グループ内のアイテムは互いに競合し、最大で 1 件しか選べません。どのアイテムをバックパックに入れると、これらのアイテムのコストの合計がバックパックの容量を超えず、かつ価値の合計が最大になるかを求めます。

F [k, v] を前の k グループのアイテムのコスト v で得られる最大の価値とすると、次のようになります：

F[k, v] = max{F[k − 1, v], F[k − 1, v − Ci] + Wi | item i ∈ group k}

fn group_pack(f: &mut Vec<usize>, v: usize, cost: &Vec<usize>, value: &Vec<usize>) {
    let group = cost.len();
    for j in (0..=v).rev() {
        for k in 0..group {
            if j < cost[k] {
                break;
            }
            f[j] = cmp::max(f[j], f[j - cost[k]] + value[k]);
        }
    }
}

fn test_group() {
    let v = 4;
    let n = 3;
    let cost = vec![vec![1, 2], vec![3, 4], vec![5, 6]]; //三つのグループ
    let value = vec![vec![3, 2], vec![1, 5], vec![2, 4]]; //
    let mut f = vec![0; v + 1];

    for i in 0..n {
        group_pack(&mut f, v, &cost[i], &value[i]);
    }
    dbg!(&f[v]);
}

依存関係のあるバックパック問題#

つまり、アイテム i はアイテム j に依存しており、アイテム i を選択する場合はアイテム j を選択する必要があります。

主アイテム k の「付属品集合」をまず 01 バックパックで処理し、コストが 0 から V − Ck までのすべての値に対して対応する最大価値 Fk [0 から V − Ck] を得ることができます。したがって、この主アイテムとその付属品の集合は、V − Ck + 1 個のアイテムのアイテムグループに相当し、コストが v のアイテムの価値は Fk [v −Ck] +Wk です。すなわち、元の指数級の戦略の中には多くの冗長な戦略があり、1 回の 01 バックパックを通じて主アイテム k とその付属品を V −Ck + 1 個のアイテムのアイテムグループに変換することで、グループバックパックのアルゴリズムを直接適用して問題を解決できます。

バックパック問題のまとめ（下）

  /*
 アイテム間に依存関係がある場合、例えば i が j に依存している場合、アイテム i を選択するにはアイテム j を選択する必要があります。
 http://acm.hdu.edu.cn/showproblem.php?pid=3449
 多くの箱があり、箱の中のアイテムを購入するにはまず箱を購入する必要がある、典型的な依存バックパックです。
 他のアイテムに依存しないアイテムを主アイテムと呼び、他のアイテムに依存するアイテムを付属品と呼びます。
 n 個の箱があり、各箱の中のアイテムの数は cnt[i] です。
 したがって、箱は主アイテムと呼ばれ、箱の中のアイテムは付属品と呼ばれます。
 主アイテムとその付属品の集合を考えると、2^n+1 種類の戦略があり、各戦略は互いに排他的です。したがって、これはグループバックパック問題です。
 しかし、一般的なグループバックパックのように処理することはできません。なぜなら、グループ内には 2^n+1 種類があるからです。
 しかし、コストが同じ場合は、価値が最大のものを選択することができます。したがって、グループ内の付属品を 01 バックパックで処理し、コストが v-c[i] から 0 までの最大価値を得ることができます。
 dp2[v-c[i]...0]

 */
 #include <stdio.h>
 #include <string.h>
 int dp[100000+10],dp2[100000+10];
 int box[55],cnt[55],price[55][11],value[55][11];
 inline int max(const int &a, const int &b)
 {
     return a < b ? b : a;
 }
 int main()
 {
     int n,v,i,j,k;
     while(scanf("%d%d",&n,&v)!=EOF)
     {
         memset(dp,0,sizeof(dp));
         for(i=1; i<=n; ++i)
         {
             scanf("%d%d",&box[i],&cnt[i]);
             memcpy(dp2,dp,sizeof(dp));
             for(j=1; j<=cnt[i]; ++j)
             {
                 scanf("%d%d",&price[i][j],&value[i][j]);
                 for(k=v-box[i]; k>=price[i][j]; --k)//付属品を 01 バックパックで処理し、各 dp2[k] はグループ内の一つの戦略に対応します
                     dp2[k] = max(dp2[k],dp2[k-price[i][j]]+value[i][j]);
             }
             for(k=box[i];k<=v; ++k)
                 dp[k] = max(dp[k],dp2[k-box[i]]);//容量が k の場合、i グループのアイテムを取ることで得られる最大値と取らない場合を比較します
         }
         printf("%d\n",dp[v]);
     }
     return 0;
 }