本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-29 16:06:27

分析背包的三要素

背包的三要素分别是：物品，体积和价值。

例题

例题 1

题目大意：

$n$ 个物品，选取其中若干个物品，使得对选取的这些物品 $\sum w_i\leq W$ 的前提下最大化 $\sum v_i$。

数据范围：

• $N\in[1,100]$
• $W\in[1,10^5]$
• $w_i\in[1,W]$
• $v_i\in[1,10^9]$

做法：

这道题就是一个 01 背包的板子。
我们就设 $f_{i,j}$ 为前 $i$ 个物品装入容量为 $j$ 的背包里，所能获取的最大价值。
易得状态转移方程：
$$f_{i,j}=\max(f_{i-1,j-w_i}+v_i,f_{i-1,j})$$ 由于数据范围过小，不需要使用滚动数组即可通过。
代码：

#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,W=1e5+5;
int n,w,ww[N],v[N],f[N][W];
signed main(){
	fst;
	cin>>n>>w;
	rep(i,1,n) cin>>ww[i]>>v[i];
	rep(i,1,n){
		rep(j,0,ww[i]-1) f[i][j]=f[i-1][j];
		rep(j,ww[i],w) f[i][j]=max(f[i-1][j-ww[i]]+v[i],f[i-1][j]);
	}
	cout<<f[n][w];
	return 0;
}

例题 2

题目大意：

$n$ 个物品，选取其中若干个物品，使得对选取的这些物品 $\sum w_i\leq W$ 的前提下最大化 $\sum v_i$。

数据范围：

• $N\in[1,100]$
• $W\in[1,10^9]$
• $w_i\in[1,W]$
• $v_i\in[1,10^3]$

TLE/MLE 做法：

参照上述做法，$O(NW)$ 暴力做法，但会 TLE/MLE。

正解：

注意到 $v_i$ 较小，我们可以尝试让 $v_i$ 当背包和物品的体积，$w_i$ 当价值。
我们设 $f_{i,j}$ 为前 $i$ 个物品的体积为 $j$，使最后的价值最小。
得状态转移方程：
$$f_{i,j}=\min(f_{i-1,j-v_i}+w_i,f_{i-1,j})$$ 最后直接倒序循环查找，找到第一个 $f_{n,j}\le w$ 的，直接输出即可。
代码：

#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,W=1e5+5;
int n,w,ww[N],v[N],f[N][W],sum;
signed main(){
	fst;
	cin>>n>>w;
	memset(f,0x3f,sizeof(f));
	rep(i,1,n){
		cin>>ww[i]>>v[i];
		sum+=v[i];
	}
	f[0][0]=0;
	rep(i,1,n){
		rep(j,0,v[i]-1) f[i][j]=f[i-1][j];
		rep(j,v[i],sum) f[i][j]=min(f[i-1][j-v[i]]+ww[i],f[i-1][j]);
	}
	per(i,sum,0)
		if(f[n][i]<=w){
			cout<<i;
			return 0; 
		}
	return 0;
}