完全背包

完全背包

一、问题形式

题目描述

有一个最多能装m公斤的背包,现在有n种物品,每种的重量分别是W1,W2,…,Wn,每种的价值分别为C1,C2,…,Cn。若每种物品的个数足够多,求能获得的最大总价值。

输入格式

第一行为两个整数,即m,n。
以后每行为两个整数,表示每件物品的重量和价值。

输出格式

获得的最大总价值。

样例

输入

5 5
1 1
2 2
3 3
4 4
5 5

输出

5

数据范围与提示

$ 1 \leq n \leq 100 $
$ 1 \leq m \leq 1000 $
$ 1 \leq c_i, w_i \leq 100 $

二、分析

法一

划分:

前i个背包容量j的最大价值;

阶段:

dp[i][j]:前i个背包容量j的最大价值;

转移:

i枚举数量,1~n;
j枚举容量:1~m;
k枚举选取数量的个数:0 ~ j/w[i];
每次取选与不选商品的最大值;
状态转移方程:
$ dp[i][j] = \max{dp[i - 1][j - k * w[i]] + c[i]} $

法二

思路:

因为k件数是有限的,即可将k消掉;

划分:

前i个背包容量j的最大价值;

阶段:

dp[i][j]:前i个背包容量j的最大价值;

转移:

i枚举数量,1~n;
j枚举容量:1~m;
每次取取与不取商品的价值最大值;
d p [ i ] [ j ] = { d p [ i − 1 ] [ j ] ( j < w [ i ] ) max ⁡ { d p [ i ] [ j − w [ i ] + c [ i ] , d p [ i − 1 ] [ j ] } ( j > = w [ i ] ) dp[i][j] = \begin{cases} dp[i - 1][j] & (j < w[i]) \\ \max\{dp[i][j - w[i] + c[i], dp[i - 1][j]\} & (j >= w[i]) \end{cases} dp[i][j]={dp[i−1][j]max{dp[i][j−w[i]+c[i],dp[i−1][j]}​(j<w[i])(j>=w[i])​

法三

思路:

背包个数那一维,只用到了i - 1,所以用滚动数组优化;

划分:

容量j的最大价值;

阶段:

dp[j]:容量j的最大价值;

转移:

i枚举数量,1~n;
j用j-w[i],从小到大枚举;
j枚举容量:w[i] ~ m;
每次比较取与不取时的价值最大值;
状态转移方程:
$ dp[j] = \max{dp[j], dp[j - w[i]] + c[i]} $

三、代码

法一

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, w[105], c[105], dp[105][1005];
int main() {
	scanf("%d %d", &m, &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &w[i], &c[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int k = 0; k <= j / w[i]; k++) {
				dp[i][j] = max (dp[i][j], dp[i - 1][j - k * w[i]] + k * c[i]);
			}
		}
	}
	printf("%d", dp[n][m]); 
	return 0;
}

法二

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, w[105], c[105], dp[105][1005];
int main() {
	scanf("%d %d", &m, &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &w[i], &c[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (j < w[i]) {
				dp[i][j] = dp[i - 1][j];
			} else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + c[i]);
			}
			
		}
	}
	printf("%d", dp[n][m]);
	return 0;
}

法三

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, w[105], c[105], dp[1005];
int main() {
	scanf("%d %d", &m, &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &w[i], &c[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]] + c[i]);
		}
	}
	printf("%d", dp[m]);
	return 0;
}

上一篇:十年磨一剑,SparkSQL来一题!


下一篇:Acwing 动态规划打卡