Skip to content

Latest commit

 

History

History
304 lines (244 loc) · 7.51 KB

背包问题.md

File metadata and controls

304 lines (244 loc) · 7.51 KB

参考：背包九讲2.0

$01$背包：

一般解法和空间优化比较熟悉，略过，这里仅记一下初始化时的一个小问题.

对于要求恰好装满背包时，我们可以在初始化时令$F[0] = 0$，$F[1...V]$均为$-\infty$，其中$V$是背包容量，$F$是状态数组.

而在没有要求恰好装满背包时，则可以全部初始化为$0$.

可以这样理解其中的区别：初始化的$F$数组是没有任何物品放入背包时的解，在要求恰好装满的情况下，除了$0$以外的其他容量均没有合法的解，而如果不要求装满，那么没有装入任何物品时，所有容量的背包都有一个合法的零解.

完全背包问题：

给出$N$种物品，每种物品有无限个，给出每种物品的体积$C_i$和价值$W_i$，给出背包的容量$V$，求不超过背包容量的情况下不断装入物品，可以得到的最大价值。

思路：

首先我们考虑最基本的转移方程：

令$F[i][j]$表示考虑前$i$件物品，背包容量为$j$时的最大价值，有：

$$ F[i][j] = max{F[i - 1][j - kC_i] + kW_i | 0 \leq kC_i \leq j} $$

我们用更清晰的形式写出来：

$$ F[i][j] = max{F[i - 1][j],F[i - 1][j - C_i] + W_i,F[i - 1][j - 2C_i] + 2W_i,...,F[i - 1][j - kC_i] + kW_i} $$ $$

F[i][j - C_i] = max{\qquad F[i - 1][j - C_i],F[i - 1][j - 2C_i] + W_i,...,F[i - 1][j - kC_i] + (k - 1)W_i} $$ 把两个式子综合一下，得到：

$$ F[i][j] = max{F[i - 1][j],F[i][j - C_i] + W_i} $$ 消去第一维，得到：

$$ F[j] = max{F[j],F[j - C_i] + W_i} $$ 从代码上来看，只需调转$01$背包中第二层循环的枚举顺序：

for(int i = 1; i <= N; i ++ )
{
    for(int j = C[i]; j <= V; j ++ )
    {
        F[j] = max(F[j],F[j - C[i]] + W[i]); 

    }
}

我们也可以从另一个角度来理解这个方程：当我们考虑$F[i][j]$时，需要的是已经选入第$i$件物品的子结果$F[i - 1][j - C_i]$，因此在一维的情况下，正序枚举容量时，$F[j - C_i]$已经是一个考虑过选入$C_i$的子结果，因此转移方程成立。

例题

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout << #x << " = " << x << endl;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pll pair<ll,ll>
#define ld long double
#define ull unsigned long long
#define pb push_back
#define INF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
const ll N = 1000 + 5;
const ll M = 1e4 + 5;
ll n,V;
ll v[N],w[N];
ll f[N];
int main()
{
	cin >> n >> V;
	for(ll i = 1; i <= n; i ++ )
	{
		cin >> v[i] >> w[i];
	}
	for(ll i = 1; i <= n; i ++ )
	{
		for(ll j = v[i]; j <= V; j ++ )
		{
			f[j] = max(f[j],f[j - v[i]] + w[i]);
		}
	}
	cout << f[V] << endl;
}

多重背包问题：

多重背包与完全背包的区别是：每种物品有$M_i$件可以取，而不是无穷件.

其基本转移方程和完全背包类似：

$$ F[i][j] = max{F[i - 1][j - kC_i] + kW_i | 0 \leq k \leq M_i} $$ 第一种算法：

如果我们将每种物品分解成$M_i$件物品，那么问题可以转化为$01$背包问题，但是这样复杂度太高了，所以不能直接这样分解。

考虑到，从$2^0,2^1,2^2,...,2^{k - 1}$中选出若干个数相加，可以表示出$0...2^k - 1$间的任意整数.进一步地，我们求出满足$2^0 + 2^1 + 2^2 + ... + 2^p \leq C_i$的最大整数$p$，令$R_i = C_i - 2^0 - 2^1 - ... - 2^p = C_i - 2^{p + 1} + 1$.

$1.$根据$p$的最大性，有$2^0 + 2^1 + ... + 2^{p + 1} > C_i$，得$2^{p + 1} > R_i$，故$2^0 + 2^1 + 2^2 + ... + 2^p$可以表示$[0,R_i]$的任意整数.

$2.$用$2^0,2^1,...,2^p,R_i$可以表示$[R_i,R_i + 2^{p + 1} - 1]$的任意一个数，而根据$R_i$的定义，$R_i + 2^{p + 1} - 1 = C_i$，故使用$2^0,2^1,...,2^p,R_i$可以表示$[R_i,C_i]$的任意整数.

综上，$2^0,2^1,...,2^p,R_i$可以且仅可以表示$[0,C_i]$间的任意整数，所以我们可以将$C_i$件物品按其进行分解为$log_2(Ci)$件：$2^0 * C_i,2^1 * C_i,...,2^p * C_i,R_i * C_i$，然后按$01$背包进行求解.

例题

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout << #x << " = " << x << endl;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pll pair<ll,ll>
#define ld long double
#define ull unsigned long long
#define pb push_back
#define INF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
const ll N = 2e4 + 5;
const ll M = 1e4 + 5;
const ll mod = 2147483648;
ll n,V;
ll f[N];
ll v[N],w[N];
int main()
{
	cin >> n >> V;
	ll cnt = 0;
	for(ll i = 1; i <= n; i ++ )
	{
		ll tv,tw,ts;
		cin >> tv >> tw >> ts;
		ll k = 1;
		while(k <= ts)
		{
			cnt ++ ;
			v[cnt] = k * tv;
			w[cnt] = k * tw;
			ts -= k;
			k *= 2;
		}
		if(ts > 0)
		{
			cnt ++ ;
			v[cnt] = ts * tv;
			w[cnt] = ts * tw;
		}
	}
	for(ll i = 1; i <= cnt; i ++ )
	{
		for(ll j = V; j >= v[i]; j -- )
		{
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	cout << f[V] << endl;
}

第二种算法：

当我们只考虑“给出的物品能否填满指定容量的背包”而不关注最大价值，即只关注问题的可行性时，多重背包有一个$O(VN)$的算法.

令$F[i][j]$表示“使用前$i$种物品填满容量为$j$的背包后，最多还剩下多少件物品$i$可用”，$F[i][j] = -1$表示这种状态不可行.

显然，转移时有两种情况：

$1.$使用前$i - 1$种物品就填满了容量$j$.

$2.$使用了第$i$种物品，那么对当前容量$j$，只有当$j - C_i$有解时，当前状态才有解.

我们可以采用贪心策略，转移时尽量选第一种，第一种不可行时再选第二种.

代码：

memset(F, -1, sizeof F);
F[0][0] = 0;
for(int i = 1; i <= N; i ++ )
{
    for(int j = 0; j <= V; j ++ )
    {
        if(F[i - 1][j] >= 0)
        {
            F[i][j] = M[i];
        }
        else
        {
            F[i][j] = -1;
        }
    }
    for(int j = 0; j <= V - C[i]; j ++ )
    {
        if(F[i][j] > 0)
        {
            F[i][j + C[i]] = max(F[i][j + C[i]], F[i][j] - 1);
        }
    }
}

例题

以下代码中由于空间限制，将状态数组拆成了两个，$used$数组表示在第$i$个阶段凑满面值$j$的硬币最少要用第$i$种硬币的数量，其余的逻辑和上面是类似的.

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout << #x << " = " << x << endl;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pll pair<ll,ll>
#define ld long double
#define ull unsigned long long
#define pb push_back
#define INF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
const ll N = 2e5 + 5;
const ll M = 1e4 + 5;
const ll mod = 2147483648;
int n,m;
int f[N],used[N];
int a[N],c[N];
void work()
{
	for(int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
	}
	for(int i = 1; i <= n;i ++ )
	{
		cin >> c[i];
	}
	for(int i = 0; i <= m; i ++ )
	{
		f[i] = 0;
	}
	f[0] = 1;
	for(int i = 1; i <= n; i ++ )
	{
		for(int j = 0; j <= m; j ++ )
		{
			used[j] = 0;
		}
		for(int j = a[i]; j <= m; j ++ )
		{
			if(!f[j] && f[j - a[i]] && used[j - a[i]] < c[i])
			{
				f[j] = 1;
				used[j] = used[j - a[i]] + 1;
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= m; i ++ )
	{
		ans += f[i];
	}
	cout << ans << endl;
}
int main()
{
	while(cin >> n >> m )
	{
		if(n == 0 && m == 0)break;
		work();
	}
}

第三种算法：

我们可以通过单调队列优化问题，可以得到一个$O(NV)$的解法.