动态规划——01背包问题（C++实现）-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划——01背包问题（C++实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述：

动态规划——01背包问题（C++实现）

解题思路：

整体思路：

利用动态规划，其目的就是将原问题分解成几个子问题，通过求解简单的子问题，把原问题给解决，就比如斐波那契数列方程：
f[i]=f[i-1]+f[i-2];
动态规划的核心就是找到原问题与子问题的关系，并列出动态转移方程。

实现方法：

这里我们可以定义一个二维数组，dp[i][j]表示对于背包容量为j的背包，前i个物品的最优解，即最大价值。
对于一个物品，可以分两种情况：
不选：对于dp[i][j]，不选第i个物品时，dp[i][j]的最优解就是dp[i-1][j]的最优解
选：如果选择，我们就让背包容量减去第i件的物品体积，让dp加上物品价值，即dp[i][j]=dp[i-1][j-v[i]]+w[i];
这样我们就得到了状态转移方程，如果要计算对于前N个物品背包容量为V的背包的最优解，只需要一层一层往前推，通过前面的子问题，求得最终答案。

状态转移方程:

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

代码和注释：

#include <iostream>
using namespace std;
int dp[1010][1010];
int v[1010],w[1010];//体积和价值
int main(){
	int N,V;
	int i,j;
	//输入数据
	cin>>N>>V;//商品个数和背包容量
	for(i=1;i<=N;i++)
	{
		cin>>v[i]>>w[i];//体积和价值
	}
	for(i=1;i<=N;i++)//依次遍历从第1个物品到第N个物品
	{
		for(j=1;j<=V;j++)//依次遍历从0~背包容量V
		{
			if(j<v[i])//如果背包容量小于物品体积
			{
				dp[i][j]=dp[i-1][j];//最优解就是上一个物品时的最优解
			}
			else//否则就是背包容量大于等于物品体积
			{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);//拿或者不拿，选最优
			}
		}
	}
	cout<<dp[N][V]<<endl;//输出前N个商品,背包容量为V的最优解
	return 0;
}