动态规划（01背包问题)

题目内容

你有一个背包，最多能容纳的体积是V。
现在有n个物品，第i个物品的体积为Vi,价值为Wi
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？

题目分析

物品	体积V	价值W
1	2	5
2	1	3
3	3	4

如果背包体积为4
（1）可以选择物品1、2体积和为3总价值为8
（2）可以选择物品2、3体积和为4总价值为7

未装满情况

思路一

每种物品只有选与不选两种情况，因此我们可以假设一个状态dp[i]表示在前i个物品中挑选若干个物品，使价值最大。

因此dp[i]可以分两种情况

（1）不选i物品总价值（等于第i-1个物品的状态表示）：dp[i-1]
（2）选i物品总价值（等于第i-1个物品的状态加i物品的价值）：dp[i-1]+w[i]

dp[i]=max(dp[i-1],dp[i-1]+w[i]);

但是能选i物品的前提条件是：在前i-1个物品选完后所剩余的空间要大于等于第i个物品所需要的空间，因此我们要引入新变量记录选到i物品后背包所剩余的空间。

思路二

在思路一的基础上引入新变量j记录背包剩余空间
dp[i][j]表示在前i个物品中挑选若干个物品，体积不超过j的最大价值

因此dp[i][j]依旧可以分两种情况

（1）不选i物品总价值：dp[i-1][j]
（2）选i物品且体积不超过j的总价值：dp[i-1][j-v[i]]+w[i]
dp[i-1][j-v[i]]表示选完第i-1个物品后体积不大于j-v[i]并且j-v[i]>=0确保第i个物品能放入背包

dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

dp[i][j]大致填表顺序

从上一排往下一排
在这里插入图片描述

填表前初始化

物品编号从1开始，引入物品0是为了防止i-1越界，而dp[0][j]可以表示挑选0个物品体积不超过（0，1，2，3，4）的最大价值，没有物品可选因此价值为0。因此初始dp表内的值全为0

返回值

dp[n][v];
n:最后一个物品
v:背包容量

代码实现

#include <cstring>
using namespace std;
const int N = 100;
int w[N], v[N];
int dp[N][N];

int main()
{
	int n, V;//物品数量，背包空间
	cin >> n >> V;
	for (int i = 1;i <= n;i++)
		cin >> w[i] >> v[i];
	//dp[i][j]表示选到第i个物品时，体积不超过j的最大价值
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= V;j++)
		{
			dp[i][j] = dp[i - 1][j];//不选择i
			if (j - v[i] >= 0)//选i
				dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
		}
	}
	cout << dp[n][V] << endl;
	return 0;
}

滚动数组优化

由于dp表填表顺序是一排一排往下填，因此第i排只会影响第i+1排数据，因此更新完第i+1排数据后便可覆盖第i排数据，类似滚轮游戏，因此我们可以用一维dp表替代二维节约内存。

在这里插入图片描述

并且更新dp[i][j]时依赖dp[i][j]的最上面的dp[i-1][j]的值以及其左上角的dp[i-1][j-v[i]],并且填入dp[i][j]时会将dp[i][j-1]覆盖，为了填表正确，必须从右往左更新

在这里插入图片描述
细节问题：当空间j小于v[i]时表示背包无法放入i物品因此不需要更新

优化代码

//区别二维只需删除i即可
#include<iostream>
using namespace std;
const int N = 100;
int w[N], v[N];
int dp[N];
int main()
{
	int n, V;
	cin >> n >> V;
	for (int i = 1;i <= n;i++)
		cin >> w[i] >> v[i];
	//dp[i][j]表示选到第i个物品时，体积不超过j的最大价值
	for (int i = 1;i <= n;i++)
	{
		for (int j = V;j >= v[i];j--)//从右往左更新
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		
	}
	cout << dp[V] << endl;
	return 0;
}

恰好装满情况

区别未装满情况只需更改一些细节问题
dp[i][j]表示在前i个物品中挑选若干个物品，体积等于j的最大价值

初始化

dp[0][j]表示挑选0个物品体积刚好为（0，1，2，3，4）除了0都不符合条件将其初始化为-1或INT_MIN(无穷小)防止对填表有影响
在这里插入图片描述

代码实现

#include<iostream>
using namespace std;
const int N = 100;
int w[N], v[N];
int dp[N][N];

int main()
{
	int n, V;
	cin >> n >> V;
	for (int i = 1;i <= n;i++)
		cin >> w[i] >> v[i];
	//dp[i][j]表示选到第i个物品时，体积不超过j的最大价值
	for (int i = 1;i <= V;i++)
	//选择0个物品体积等于j不存在初始化为-1目的与的dp[0][0]=0区分
		dp[0][i] = -1;
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= V;j++)
		{
			dp[i][j] = dp[i - 1][j];//不选择i
			if (j - v[i] >= 0&&dp[i-1][j-v[i]]!=-1)//比未装满多一个限定条件
				dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
		}
	}
	cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
	//判定物品是否能恰好装满，不能则返回0

	return 0;
}

滚动数组优化

#include<iostream>
using namespace std;
const int N = 100;
int w[N], v[N];
int dp[N];
int main()
{
	int n, V;
	cin >> n >> V;
	//dp[i][j]表示选到第i个物品时，体积不超过j的最大价值
	for (int i = 1;i <= V;i++)
	//选择0个物品体积等于j不存在初始化为-1目的与的dp[0][0]=0区分
		dp[i] = -1;
	for (int i = 1;i <= n;i++)
	{
		for (int j = V;j >= v[i];j--)
		 if (dp[j - v[i]] != -1)
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
	}
	cout << (dp[V] == -1 ? 0 : dp[V]) << endl;

	return 0;
}