0-1背包问题

题目链接：https://www.acwing.com/problem/content/description/2/

题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入描述

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出描述

输出一个整数，表示最大价值。
0<N,V≤1000
0<vi,wi≤1000

示例

输入

4 5
1 2
2 4
3 4
4 5

输出

8

分析

约定

我们记第i件物品的体积和价值为v[i],w[i]

状态表示

f(i,j)表示满足如下条件的方案的最大价值：

• 仅从前i件物品中选择
• 所选取的物品体积小于等于j

状态划分

对于f(i,j),存在两种情况：

• 选了第i件物品
• 没选第i件物品

状态转移方程

对应状态划分，我们便可以得到相应的状态转移方程：

• f(i,j)=f(i-1,j)
• f(i,j)=f(i-1,j-v[i])+w[i]

显然，我们要取的f(i,j)应当是两者的最大值，因此最终的状态转移方程如下：
f(i,j)=max(f(i-1,j),f(i-1,j-v[i])+w[i])

总结

以上，是以f(i,j)这样一个二维的函数来求解本问题的思路，我们可以想象出一张二维的表格，行对应i，列对应j，求解的过程其实就是一行一行填表的过程，不断利用之前求出的结果，最终得到最终答案。

优化

对于这样一个填表的过程，由状态转移方程可以发现，要得到新的一行数据，只需要上一行的数据，我们没有必要将每一行数据都保存下来，因此我们就可以将二维的状态表示优化成一维的，在原有思路的指导下做出改变。改动时的易错点见代码注释。

二维解法AC代码

---

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1001;
int n, V;
int v[N], w[N];
int f[N][N];

int main()
{
	cin >> n >> V;

	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= V; 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][V] << endl;
	return 0;
}

一维解法AC代码

---

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1001;
int n, V;
int v[N], w[N];
int f[N];

int main()
{
	cin >> n >> V;

	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];

	for (int i = 1; i <= n; i++)
	{
		for (int j = V; j >= v[i]; j--)
		{
            //f[j]=f[j] 对应二维，应是我们思维的一步，理解后可去掉
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}

    //第二维的循环顺序改为由后向前，且终点改为了v[j]
    /*顺序更改：得到新行需要上一行的数据(某一元素正上方的数据和左上方的数据)，因此如果继续从前向后，会覆盖上一行的数据，致使新行后面的数据无法计算*/
    /*终点更改：防止越界*/

	cout << f[V] << endl;
	return 0;
}