本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-30 11:15:32

背包的转化

并不是所有的背包都那么明显，有时候需要进行转化。

例题 1：

例题 1

题目大意：

有 $n$ 个物品，每个物品要么花费 A 代价 $t_i$ 元，要么花费 B 代价 $w_i$ 元，使最后的总代价 A 比 B 大，求最小的总代价 A。

数据范围：

• $n\in[1,100]$
• $t_i\in\{1,2\}$
• $w_i\in[1,100]$

做法：

我们可以设 $f_{i,j,k}$ 为前 $i$ 个物品，花费了 A 代价 $j$ 元，B 代价 $k$ 元的可行性，可行为 $1$，不可行为 $0$，边界条件为 $f_{0,0,0}=1$。
推出转移方程：
$$f_{i,j,k}=\begin{cases}1&j\ge t_i\land f_{i-1,j-t_i,k}\
&k\ge w_i\land f_{i-1,j,k-w_i}\&otherwise\end{cases}$$ 最后倒序循环枚举 $f_{n,i,j}$，找到第一个可行的直接输出 $i$ 即可。
总体时空复杂度为 $O(n(\sum t_i)^2)$。
代码：

#include<bits\/stdc++.h>
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define repe(i,x,y,z) for(int i=x;i<=y;i+=z)
#define eper(i,x,y,z) for(int i=x;i>=y;i-=z)
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define inl inline
#define INF LLONG_MAX
using namespace std;
const int N=105,T=205;
int n,t[N],w[N],sum;
bool f[N][T][T];
signed main(){
	fst;
	cin>>n;
	rep(i,1,n){
		cin>>t[i]>>w[i];
		sum+=t[i];
	}
	f[0][0][0]=1;
	rep(i,1,n)
		rep(j,0,sum)
			rep(k,0,sum){
				if(j>=t[i]) f[i][j][k]|=f[i-1][j-t[i]][k];
				if(k>=w[i]) f[i][j][k]|=f[i-1][j][k-w[i]];
			}
	rep(i,0,sum)
		rep(j,0,i)
			if(f[n][i][j]){
				cout<<i;
				return 0;
			}
	return 0;
}