背包

易错点

  • 初值如：（0 ，1）/（-1 ，1e9 ,0)......

  • 递推方程

  • 边界问题是否出界

0-1背包

两种表达方式

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int main() {
	int n ,m;
	cin >> n >> m;
	int dp[2000][2000]={0};
	//dp[i][j]为前i个物体，用j体积最大价值
	int w[2000] ,v[2000];
	memset(dp ,-1, sizeof(dp));//dp[][]==-1表示不可能
	dp[0][0]=0;//特殊的没用物体，用0体积可能，但价值为0
	for(int i=1;i<=n;i++)
		cin >> w[i] >> v[i];
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++)
			if(j >= w[i])
				dp[i][j]=max(dp[i-1][j] ,dp[i-1][j-w[i]] + v[i]);//递推方程：1.取第i个物或不取体
			else 
				dp[i][j]=dp[i-1][j];//2.没办法取
	}
	int ans=0;
	for(int i=1;i<=m;i++)
		ans=max(ans ,dp[n][i]);
	cout << ans<<endl;
    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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n, m, w[405], v[405];
//dp[i][j]为前i个物体贡献j价值时的最小体积
//9e18表示该情况不可能
long long dp[405][40005];
const long long LIM = 9000000000000000000ll;
int main() 
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	//初值前0物体可以贡献0价值，其他情况先设为不可能
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n * 100; j++)
			dp[i][j] = LIM;
	dp[0][0] = 0;
	//递推，依次算出每个子问题的最优，一个不漏
	for (int i = 1; i <= n; i++){//前i个物体
		for (int j = 0; j <= n * 100; j++){//恰好j价值
			//现在dp[i][j] = LIM表示不可能。分别考虑两种情况能不能得到dp[i][j]
			
			//j价值够第i个，而且剩下的体积能被前i-1个恰好占满，才可以取i
			if (j >= v[i] && dp[i - 1][j - v[i]] != LIM)
				dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
			//j能被前i-1个恰好占满，才可以不取i
			if (dp[i - 1][j] != LIM)
				dp[i][j] = min(dp[i][j], dp[i - 1][j]);
			//若两种情况都不可能，则仍有dp[i][j] = LIM
		}
	}
	//答案,从大到小找第一个m体积够装的价值
	for (int j = 100 * n; j >= 0; j--)
		if (dp[n][j] <= m){//说明j价值能在m体积内得到
			cout << j << endl;
			break;
		}
	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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n, m, w[805], v[805];
int dp[300005] = {0}, dp2[300005];
int main() 
{
	// memset(a, 0, sizeof(a));//把数组a初值设为0
	// memcpy(b, a, sizeof(a));//把数组a复制进b
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d %d", &w[i], &v[i]);
	//递推，依次算出每个子问题的最优，一个不漏
	for (int i = 1; i <= n; i++){//前i个物体
		//dp[]相当于原先的dp[i-1][]
		//dp复制进dp2，则dp2[]相当于原先的dp[i-1][]
		memcpy(dp2, dp, sizeof(dp));
		//dp2更新dp，则dp变为原先的dp[i][]
		for (int j = 0; j <= m; j++){//恰好j体积
			dp[j] = dp2[j];//先把dp[j]设为不取i的情况
			//再用取i的情况挑战一下
			if (j >= w[i] && dp2[j - w[i]] != -1)
				dp[j] = max(dp[j], dp2[j - w[i]] + v[i]);
		}
	}
	//答案
	int ans = 0;
	for (int j = 0; j <= m; j++)
		ans = max(ans, dp[j]);
	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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n, m, w[505], v[505];
//dp[i][j]为前i个物体占j体积时的最大价值
//-1表示该情况不可能
int dp[505][5005];
int main() 
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	//初值0物体可以占用0体积，其他情况先设为不可能
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	//递推，依次算出每个子问题的最优，一个不漏
	for (int i = 1; i <= n; i++){//前i个物体
		for (int j = 0; j <= m; j++){//恰好j体积
			//现在dp[i][j] = -1表示不可能。分别考虑两种情况能不能得到dp[i][j]
			
			//j体积够装第i个，而且剩下的体积能被前i-1个恰好占满，才可以取i
			if (j >= w[i] && dp[i][j - w[i]] != -1)
				dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
			//j能被前i-1个恰好占满，才可以不取i
			if (dp[i - 1][j] != -1)
				dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			//若两种情况都不可能，则仍有dp[i][j] = -1
		}
	}
	//答案
	int ans = 0;
	for (int j = 0; j <= m; j++)
		ans = max(ans, dp[n][j]);
	cout << ans << endl;
	return 0;
 }

压缩储存版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n, m, w[505], v[505];
int dp[5005] = {0};
int main() 
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	for (int i = 1; i <= n; i++)
		for (int j = w[i]; j <= m; j++)
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	
	cout << dp[m] << endl;
	return 0;
}

伴随背包

0-1背包方案数

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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n, m, w[1005], v[1005];
//dp[i][j]为前i个物体占j体积时的最大价值
//-1表示该情况不可能,cnt[i][j]为实际达到dp[i][j]的方案数
int dp[1005][1005], cnt[1005][1005];
int main() 
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	//初值0物体可以占用0体积，其他情况先设为不可能
	memset(dp, -1, sizeof(dp));
	memset(cnt, 0, sizeof(cnt));
	dp[0][0] = 0, cnt[0][0] = 1;
	//递推，依次算出每个子问题的最优，一个不漏
	for (int i = 1; i <= n; i++){//前i个物体
		for (int j = 0; j <= m; j++){//恰好j体积
			if (j >= w[i] && dp[i - 1][j - w[i]] != -1)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
			//j能被前i-1个恰好占满，才可以不取i
			if (dp[i - 1][j] != -1)
				dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			//在dp[i][j]最终决定后，再决定cnt
			if (j >= w[i] && dp[i - 1][j - w[i]] != -1 && dp[i][j] == dp[i - 1][j - w[i]] + v[i])
				cnt[i][j] += cnt[i - 1][j - w[i]];
			if (dp[i - 1][j] != -1 && dp[i][j] == dp[i - 1][j])	
				cnt[i][j] += cnt[i - 1][j];
		}
	}
	//答案
	int ans = 0;//最大价值
	for (int j = 0; j <= m; j++)
		ans = max(ans, dp[n][j]);
	int ans2 = 0;//方案数
	for (int j = 0; j <= m; j++)
		if (dp[n][j] == ans)
			ans2 += cnt[n][j];
	cout << ans2 << endl;
	return 0;
}

0-1背包最大体积

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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n, m, w[1005], v[1005];
//dp[i][j]为前i个物体占j体积时的最大价值-1表示该情况不可能
//mx[i][j]为实际达到dp[i][j]的最大单个物品体积
int dp[1005][1005], mx[1005][1005];
int main() 
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	//初值0物体可以占用0体积，其他情况先设为不可能
	memset(dp, -1, sizeof(dp));
	memset(mx, 0, sizeof(mx));
	dp[0][0] = 0, mx[0][0] = 0;
	//递推，依次算出每个子问题的最优，一个不漏
	for (int i = 1; i <= n; i++){//前i个物体
		for (int j = 0; j <= m; j++){//恰好j体积
			if (j >= w[i] && dp[i - 1][j - w[i]] != -1)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
			//j能被前i-1个恰好占满，才可以不取i
			if (dp[i - 1][j] != -1)
				dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			//在dp[i][j]最终决定后，再决定cnt
			if (j >= w[i] && dp[i - 1][j - w[i]] != -1 && dp[i][j] == dp[i - 1][j - w[i]] + v[i])
				mx[i][j] = max(mx[i][j], max(mx[i - 1][j - w[i]], w[i]));
			if (dp[i - 1][j] != -1 && dp[i][j] == dp[i - 1][j])	
				mx[i][j] = max(mx[i][j], mx[i - 1][j]);
		}
	}
	//答案
	int ans = 0;//最大价值
	for (int j = 0; j <= m; j++)
		ans = max(ans, dp[n][j]);
	int ans2 = 0;//体积
	for (int j = 0; j <= m; j++)
		if (dp[n][j] == ans)
			ans2 = max(ans2, mx[n][j]);
	cout << ans2 << endl;
	return 0;
}

0-1背包最少物体数

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int main() {
	int n ,m;
	cin >> n >> m;
	int dp[2000][2000]={0};
	int cnt[2000][2000]={0};
	int w[2000] ,v[2000];
	memset(dp ,-1, sizeof(dp));
	dp[0][0]=0;
	cnt[0][0]=0;
	for(int i=1;i<=n;i++)
		cin >> w[i] >> v[i];
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(j >= w[i] && dp[i-1][j-w[i]]!=-1){
				if(dp[i-1][j] > dp[i-1][j-w[i]]+v[i])
					dp[i][j]=dp[i-1][j] ,cnt[i][j]=cnt[i-1][j];
				else if(dp[i-1][j] < dp[i-1][j-w[i]]+v[i])
					dp[i][j]=dp[i-1][j-w[i]]+v[i] ,cnt[i][j]=cnt[i-1][j-w[i]]+1;
				else 
					dp[i][j]=dp[i-1][j] ,cnt[i][j]=min(cnt[i-1][j] ,cnt[i-1][j-w[i]]+1);
			}
			else
				dp[i][j]=dp[i-1][j] ,cnt[i][j]=cnt[i-1][j];
			
		}
	}
	int ans=0 ,ans2=0;
	for(int i=1;i<=m;i++){
		if(dp[n][i] > ans){ans=dp[n][i],ans2=cnt[n][i];}
		else if(dp[n][i]==ans)ans2=min(ans2 ,cnt[n][i]);
	}
	cout << ans2 <<endl;
    return 0;
}