YbtOJ「动态规划」第1章 背包问题

YbtOJ 大全

【例题1】采药问题

一道基础的 $01$ 背包模板题。

#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
   
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 1e5+10;
int t,m;
int w[M],v[M],f[M];
signed main(){
   
	t=read(),m=read();
	rep(i,1,m) scanf("%d%d",&w[i],&v[i]);
	rep(i,1,m) drep(j,t,w[i]) f[j] = max(f[j],f[j-w[i]]+v[i]);
	printf("%d\n",f[t]);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

【例题2】货币系统

可以大胆猜测，新的货币系统 $(m,b)$ 一定是原来的货币系统 $(n,a)$ 的子集。可以感性理解，如果存在一个 $w$，不在原来的货币系统 $(n,a)$ 中，那么一定会存在某些值，可以用新的货币系统表示出来但原来的货币系统不能表示。

于是问题就变成了，从 $(n,a)$ 中找一个最小的子集，满足能表示出原货币系统可以表示出的所有数。

我们把 $a_i$ 从小到大排序，然后对于每一个 $a_i$ 往后扫，把能表示出的点打上标记，最后看有多少个在原货币系统中的 $a_i$ 被打上标记，减去就是答案。

#include 
#include 
#include 
#include 
#include 
#define re register
#define int long long
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
   
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 2e5+10;
int T,n;
int f[M],a[M];
signed main(){
   
	T=read();
	while(T--){
   
		n=read();
		memset(f,0,sizeof(f));
		rep(i,1,n) a[i] = read();
		sort(a+1,a+n+1);
		f[0] = 1;
		int ans = n;
		rep(i,1,n){
   
			if(f[a[i]]) {
    ans--; continue; }
			rep(j,a[i],a[n]) f[j] |= f[j-a[i]];
		}
		printf("%d\n",ans);
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

【例题3】宝物筛选

一道多重背包模板题，最朴素的做法就是按数量每一个都拆分成一件物品。

考虑如何对这个过程优化。我们知道，$2$ 的次方相加能表示出任意的整数，所以我们可以对于这个物品的数量进行二进制拆分，最后就变成了 $01$ 背包。

#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
   
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 1e5+10;
int n,t;
int cnt;
int w[M],v[M],f[M];
signed main(){
   
	n=read(),t=read();
	rep(i,1,n){
   
		int x=read(),y=read(),z=read();
		for(re int j(1) ; j<=z ; j<<=1){
   
			v[++cnt] = x*j;
			w[cnt] = y*j;
			z -= j;
		}
		v[++cnt] = x*z;
		w[cnt] = y*z;
	}
	rep(i,1,cnt) drep(j,t,w[i]) f[j] = max(f[j],f[j-w[i]]+v[i]);
	printf("%d\n",f[t]); 
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

【例题4】硬币方案

对于每一个 $a_i$，我们可以扫出它能表示的数。设 $f[j]$ 表示 $j$ 能不能被表示出来，可以从