题意

有 $n$ 个物品，一个 $m$ 大小的背包。让背包里的价值最大

物品：有重量（占的空间） $w$ 和价值 $v$

思路

$a_{i,j}$ 的意思是第 $i$ 个重量，前 $j$ 个物品的最大价值

这个物品有两种状态：拿和不拿

拿的话就要将上一个物品丢掉，然后将这个物品装进背包（$a_{i,j} = a_{i - w_j,j - 1} + v_j$）

代码（未优化）

#include <bits/stdc++.h>
using namespace std;
int a[205][35],w[35],v[35];	// a：i 个重量，前 j 个物品时能存的最大价值
int main(int argc, char **argv){
	int n,m;
	cin >> m >> n;
	for (int i = 1;i <= n;i++){
		cin >> w[i] >> v[i];	// 重量和价值
	}
	for (int j = 1;j <= n;j++){	// 遍历物品
		for (int i = 1;i <= m;i++){	// 遍历重量
			if (i < w[j])	a[i][j] = a[i][j - 1];	// 前 w[j] 个重量时，这个物品放不下来
			else	a[i][j] = max(a[i - w[j]][j - 1] + v[j],a[i][j - 1]);	// 左边是拿这个物品，右边是不拿
		}
	}
	cout << a[m][n];
	return 0;
}

思路（新）

提问

能不能优化一下呢？

时间不能优化，因为每一个重量要从上一个物品那里拿过来，不然会影响下一个物品

那就优化空间

做法

二维数组优化到一维数组

当前物品遍历完所有重量后，到下一个物品

下一个物品算出来后直接覆盖

注意：

要从后往前遍历重量，因为从前往后遍历，就会把上一个物品的值覆盖掉，后面的重量就用不了上一个物品的数据了

代码（优化）

#include <bits/stdc++.h>
using namespace std;
int a[205],w[35],v[35];	// a 从二维数组压缩成一维
int main(int argc, char **argv){
	int n,m;
	cin >> m >> n;
	for (int i = 1;i <= n;i++){
		cin >> w[i] >> v[i];	// 重量和价值
	}
	for (int j = 1;j <= n;j++){	// 遍历物品
		for (int i = m;i >= w[j];i--){	// 为确保上一个物品的值不被覆盖，要从后往前数
			a[i] = max(a[i - w[j]] + v[j],a[i]);	// 左边是拿这个物品，右边是不拿这个物品
		}
	}
	cout << a[m];
	return 0;
}