2.3 动态规划—完全背包问题

有 N N N种物品和一个容量是 V V V的背包，每种物品都有无限件可用。第 i i i种物品的体积是 v i v_i vi​，价值是 w i w_i wi​。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

#include
#include
#define N 1010

int n, m;			//n为物品个数，m为背包总容量
int v[N], w[N];		//分别表示体积和重量
int f[N][N];		//状态函数，f[i][j]表示只考虑前i个物品且体积不超过j的最大价值
int main(){
	printf("请输入物品个数和背包容量（中间用空格隔开）：");
	scanf_s("%d %d", &n, &m);
	printf("n请输入物品体积和价值（中间用空格隔开）：n");
	for(int i = 1; i <= n; i++)
		scanf_s("%d %d", &v[i], &w[i]);
	
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= m; j++){					//完全背包二维只能正序更新，0/1背包二维更新正序/逆序都可以
			f[i][j] = f[i - 1][j];						//不选择第i个物品时
			if(j >= v[i])								//如果j>=v[i]，才能选择第i个物品
				f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
		}
	
	printf("最大价值为：%d", f[n][m]);
	return 0;
}

完全背包二维之所以只能正序更新，不能逆序更新是因为： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − v [ i ] ] + w [ i ] ) f[i][j]=max(f[i−1][j],f[i][j−v[i]]+w[i]) f[i][j]=max(f[i−1][j],f[i][j−v[i]]+w[i])想求 f [ i ] [ j ] f [ i ] [ j ] f[i][j]f[i][j] f[i][j]f[i][j]，要先求 f [ i ] [ j − v [ i ] ] f[i][j−v[i]] f[i][j−v[i]]，两者都是 f [ i ] f[i] f[i]，也就是在同一层，所以只能正序更新。

01背包二维之所以 正序逆序都可以是因为： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v [ i ] ] + w [ i ] ) f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i]) f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i])想求 f [ i ] [ j ] f[i][j] f[i][j]，要先求 f [ i − 1 ] [ j − v [ i ] ] f[i−1][j−v[i]] f[i−1][j−v[i]]，前者是 f [ i ] f[i] f[i]，后者是 f [ i − 1 ] f[i - 1] f[i−1]，不在同一层，所以 正序逆序更新都可以。

#include
#include
#define N 1010

int n, m;			//n为物品个数，m为背包总容量
int v[N], w[N];		//分别表示体积和重量
int f[N];			//状态函数，f[j]表示只考虑前i个物品且体积不超过j的最大价值
int main(){
	printf("请输入物品个数和背包容量（中间用空格隔开）：");
	scanf_s("%d %d", &n, &m);
	printf("n请输入物品体积和价值（中间用空格隔开）：n");
	for(int i = 1; i <= n; i++)
		scanf_s("%d %d", &v[i], &w[i]);
	
	for(int i = 1; i <= n; i++)
		for(int j = v[i]; j <= m; j++){					//完全背包二维只能正序更新，0/1背包二维更新正序/逆序都可以
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	
	printf("最大价值为：%d", f[m]);
	return 0;
}

#include
#include
#define N 1010

int n, m;			//n为物品个数，m为背包总容量
int v, w;			//分别表示体积和重量
int f[N];			//状态函数，f[j]表示只考虑前i个物品且体积不超过j的最大价值
int main(){
	printf("请输入物品个数和背包容量（中间用空格隔开）：");
	scanf_s("%d %d", &n, &m);
			
	for(int i = 1; i <= n; i++){
		printf("n请输入物品体积和价值（中间用空格隔开）：");
		scanf_s("%d %d", &v, &w);
		for(int j = v[i]; j <= m; j++){					//完全背包二维只能正序更新，0/1背包二维更新正序/逆序都可以
			f[j] = max(f[j], f[j - v] + w);
		}
	}
	printf("最大价值为：%d", f[m]);
	return 0;
}