アルゴリズム導論学習ノート(十三):動的計画(三):01リュックサック問題

01リュックサックの問題
N個の品物とV容量のリュックサックがあります.i番目の品物の体積はc[i]、価値はw[i]です.リュックサックにどのアイテムを入れるかを解くと、価値の合計が最大になります.
基本的な考え方
これは最も基礎的なリュックサックの問題で、特徴は:すべての品物は1つしかなくて、置くか置かないかを選ぶことができます.サブ問題で状態を定義する:すなわちf[i][v]は前のi件の物品を表す
容量vのリュックサックを適当に入れると最大の価値が得られます.状態遷移方程式は次のとおりです.
f[i][v] = max{f[i-1][v],f[i-1][v-c[i]]+w[i]}.
この方程式は非常に重要であり,基本的にリュックサック問題に関連する問題の方程式はすべてそれから派生した.詳しく説明する必要があります
下:前のi品を容量vのリュックサックに入れるというサブ問題は、i品目の戦略(置くか置かないか)だけを考慮すると、1つの
前i-1件の物品に関する問題.i番目のアイテムを置かないと、問題は前のi-1アイテムが容量vのリュックサックに入れられ、価値はf[i-1][v]になる.
i番目のアイテムを置くと、問題は前のi-1アイテムに変換され、残りの容量v-c[i]のリュックサックに入れると、このとき得られる最大の価値は:
f[i-1][v-c[i]]+w[i].
スペースの複雑さの最適化
以上の方法の時間的複雑度と空間的複雑度はいずれもO(VN)であり,時間的複雑度はこれ以上最適化できないはずであるが,空間的複雑度は最適化できる.
O(N)まで.まず、上記の基本的な考え方をどのように実現するかを考えてみると、主循環i=1に違いありません.Nは、f[i][0...V]の全ての値を毎回算出する.では、もし
1つの配列f[0...V]で?f[i][v]はf[i-1][v]とf[i-1][v-c[i]]の2つのサブ問題から繰り返され、f[i][v]を押すとき(つまりi回目のループで押すことを保証できるかどうか
f[v]の場合)f[i-1][v]とf[i-1][v-c[i]]の値が得られますか?実際、これは主サイクルのたびにv=Vで...0の順序はf[v]を押して、このようにやっと保証することができます
f[v]を押すとf[v-c[i]]は状態f[i-1][v-c[i]]の値を保存します.疑似コードは次のとおりです.
vの順序を上の逆順に変更すると、v=0...Vの場合、f[i][v]はf[i][v-c[i]]から発売され、本題とは意味が合わない.
≪インスタンス｜Instance｜emdw≫
理論を話し終わったら、実際の例を見てみましょう.次の例は杭電ACMの原題:Bone Collectorです.次は私のACコードです.

#include
using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int N, V;
        int value[1001], volume[1001];
        cin >> N >> V;
        for (int i = 0; i < N; i++)
        {
            cin >> value[i];
        }
        for (int i = 0; i < N; i++)
        {
            cin >> volume[i];
        }

        int f[1001] = {0};
        for (int i = 0; i < N; i++)
        {
            for (int v = V; v >= volume[i]; v--)
            {
                f[v] = max (f[v], f[v-volume[i]]+value[i]);
            }
        }

        cout << f[V] << endl;
    }
    return 0;
}

上の問題は単純に与えられた繰返し式を組み合わせるだけでいいので、次の問題は私たちが少し変える必要があります:Robberies.私のACコード:

#include
using namespace std;

double max (double a, double b)
{
	return a > b ? a : b;
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		double cp;
		double p[10001];  //          N < 100，      1001   ，                  
		int a[10001];
		double f[10001];
		int n;
		cin >> cp >> n;
		int m = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> a[i] >> p[i];
			m += a[i];
		}

		memset(f,0,sizeof(f));
		f[0] = 1;
		for (int i = 0; i < n; i++)
		{
			for (int j = m; j >= a[i]; j--)
			{
				f[j] = max(f[j], f[j - a[i]] * (1 - p[i]));
			}
		}

		int i;
		for (i = m; i >= 0; i--)
		{
			if (f[i] >= 1 - cp)
				break;
		}
		cout << i << endl;
	}
	return 0;
}