问题引入

假设一个飞檐走壁的小偷，背着一个可装4磅东西的背包， 潜入一个房间，可以盗窃如下三件商品：

为了让盗窃的商品价值最高，你应该盗窃哪些商品？最简 单的算法：尝试各种可能的商品组合，并找出价值最高的组合。

方案虽然可行，但是效率非常低！如果3件商品，需要计算8种组合情况，4件商品，需要计算16种组合情况，n件商品， 一共2的n次方种情况。那么，如何找到最优解？使用动态规 划!动态规划算法原理：先解决子问题，再逐步解决大的问题。对于背包问题，先解决（子背包）问题！

网格解题法

对于每一种物品，都有选和不选两种决策。

选第i种商品：f[i][j] = v + f[i-1][j-w]。

不选第i种商品：f[i][j] = f[i-1][j]，如果可以装下，取两者最大值。

01背包问题-模板

朴素版本-核心代码

for(int i = 1; i <= n; i++){
    int w, c;
    cin >> w >> c;
    for(int j = 1; j <= m; j++){
        if(j >= w)
            f[i][j] = max(f[i - 1][j], c + f[i - 1][j - w]);
        else
            f[i][j] = f[ i - 1][j];
    }
}

降维优化：

既然每轮答案都在上一轮的基础上更新，且最终结果只需要看最后一个解， 所以数组可以压成一维滚动数组，从而优化空间复杂度。

但是，直接将数组变为一维是否有问题？（每一行运算的结果将上一行的值替换，保证只用到一维空间）

当前f[i][j]来自于上一行f[i-1][j]以及上一行前面某个值，由于是从左至右枚举，前面的某个值已经被更新过，不再是i-1轮的结果。

for(int i = 1; i <= n; i++){
    int w, c;
    cin >> w >> c;
    for(int j = m; j >= w; j--){
        f[j] = max(f[j], c + f[j - w]);
    }
}

滚动数组优化：由于只需要当前行和上一行，可以开两个一维数组进行滚动。

for(int i = 1; i <= n; i++){
    int w, c;
    cin >> w >> c;
    for(int j = 1; j <= m; j++){
        if(j >= w)
            f[i & 1][j] = max(f[(i - 1) & 1][j], c + f[(i - 1) & 1][j - w]);
        else
            f[i & 1][j] = f[(i - 1) & 1][j];
    }
}

[USACO 08 DEC] Hay For Sale S

解析：01背包模板题。

[NOIP 2005 普及组] 采药

解析：01背包模板题。

[USACO 09 OCT] Bessie's Weight Problem G

解析：01背包模板题。

[NOIP 2001 普及组] 装箱问题

解析：01背包模板题。

[NOIP 2006 普及组] 开心的金明

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int M = 30010, N = 50;
int m, n;
int f[N][M];
int main() {
	
	scanf("%d%d", &m, &n);

	for(int i = 1; i <= n; i++){
		int w, v;
		scanf("%d%d", &w, &v);

		for(int j = 1; j <= m; j++)
			if(j >= w)
				f[i][j] = max(f[i - 1][j], w*v + f[i - 1][j-w]);
			else
				f[i][j] = f[i - 1][j];
	}

	printf("%d\n", f[n][m]);

	return 0;
}