先聊聊区分 贪心 和 01背包

背包问题：

有多个物品，重量不同、价值不同，以及一个容量有限的背包，选择一些物品装到背包中，问怎么裝才能使装进背包的物品总价值最大。根据不同的限定条件，可以把背包问题分为很多种，常见的有下面两种：

(1）如果每个物体可以切分。称为一般背包问题，用贪心法求最优解。比如吃自助餐，在饭量一定的情况下，怎么吃才能使吃到肚子里的最值钱？显然应该从最贵的食物吃起，吃完了最贵的再吃第2贵的，这就是贪心法。

(2） 如果每个物体不可分割，称为 0/1 背包问题。仍以吃自助餐为例，这次食物都是一份份的，每一份必须吃完。如果最贵的食物一份就超过了你的饭量，那只好放弃。这种问题无法用贪心法求最优解。

01背包问题

01背包是一种动态规划问题。动态规划的核心就是状态转移方程，解释01背包状态转移方程的原理。

01背包问题可描述为如下问题：

有一个容量为V的背包，还有n个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积w和价值v。

问：如何向背包装物体才能使背包中物体的总价值最大？

例题：骨头收集器

问题描述

许多年前，在泰迪的家乡，有一个人叫“骨头收集者”。这个人喜欢收集各种骨头，比如狗的、牛的，他也去坟墓......
骨头采集者有一个体积为V的大袋子，在他收集的旅途中有很多骨头，显然，不同的骨头有不同的价值和不同的体积，现在给定每块骨头沿途的价值，你能计算出骨头收集者可以得到的总价值的最大值吗？

输入

第一行包含一个整数 T ，即案例数。
后面是T个案例，每个案例三行，第一行包含两个整数N，V，（N <= 1000，V <= 1000）代表骨头的数量和他的袋子的体积。第二行包含 N 个整数，表示每个骨骼的值。第三行包含 N 个整数，表示每块骨头的体积。

输出

每行一个整数，表示总值的最大值（此数字将小于 231）。

示例输入

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

示例输出

14

原题链接：Problem - 2602 (hdu.edu.cn)

代码（二维形式）：

（二维形式）但过不了这道题！但用结构体能过！

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//#define int long long
const int N = 1010;
int v[N], w[N];
//int f[N];
int f[N][N];
int n, m;
int x, y;
int main()
{
	int t;
	cin >> t;
	while (t--) {
		memset(f, 0, sizeof f);
		memset(v, 0, sizeof v);
		memset(w, 0, sizeof w);
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
			cin >> w[i];
		for (int i = 1; i <= n; i++)
			cin >> v[i];
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				f[i][j] = f[i - 1][j];
				if (j >= v[i]) {
					f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
				}
			}
		}
		cout << f[n][m] << endl;
		
	}
	return 0;
}

一维优化（滚动数组）：

通过观察，二维f[][] [] [],每一行是从上面一行算出来的，只跟上面一行有关系，跟更前面的行没有关系。用新的一行覆盖原来的一行就可以了，所以可以把i层去掉

优化后，空间复杂度从O(NV)->O(V)。

缺点：覆盖了中间转移状态，只留下了最后的状态，所以损失了很多信息，导致无法输出背包的方案。

一维形式：能过！

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//#define int long long
const int N = 1010;
int v[N], w[N];
int f[N];
int n, m;
int x, y;
int main()
{
	int t;
	cin >> t;
	while (t--) {
		memset(f, 0, sizeof f);
		memset(v, 0, sizeof v);
		memset(w, 0, sizeof w);
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
			cin >> w[i];
		for (int i = 1; i <= n; i++)
			cin >> v[i];
		for (int i = 1; i <= n; i++)
			for (int j = m; j >= v[i]; j--)//倒过来
			{
                //f[i][j] = f[i - 1][j];i层去掉，恒等式了，删去
				f[j] = max(f[j], f[j - v[i]] + w[i]);
			}
		cout << f[m] << endl;
	}
	return 0;
}