[数据结构与算法]1.01背包动态规划方程式之进化版和完全版

#include<iostream>
using namespace std;
#include <algorithm>
//01背包动态转义方程式
//01背包 完成态
int Bag_Com();
//01背包 进化态
int Bag_Evolution();


//主函数
int main()
{
	Bag_Evolution();
	Bag_Com();
	return 0;
}

//01背包 完全版
int Bag_Com()
{
	int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
	int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
	int bagV = 8;								//背包大小
	int dp[9] = { { 0 } };			            //动态规划表

	for (int i = 1; i <= 4; i++)
	{
		//这里要从右边开始 因为j - w[i] 始终比j小 所以要用到左边的的上一层的值(必须保证在当前n层操作的时候 不要修改n层的之后需要用到的n-1层的数据)
		//而如果从左边开始 由于j - w[i] 始终比j小 所以会影响到左边的值 导致数据不是上一层的值
		for (int j = bagV; j >=0; j--)
		{
			if(j>=w[i])
				dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		}
	}
	//动态规划表的输出
	cout << "--------[01背包-完全版]--------" << endl;
	for (int j = 0; j < 9; j++)
	{
		cout << dp[j] << ' ';
	}
	cout << endl;
	return 0;
}
//01背包 进化版
int Bag_Evolution()
{
	int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
	int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
	int bagV = 8;								//背包大小
	int dp[5][9] = { { 0 } };			        //动态规划表

	for (int i = 1; i <= 4; i++)
	{
		for (int j = 1; j <= bagV; j++)
		{
			if (j < w[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
	cout << "--------[01背包-进化版]--------" << endl;
	//动态规划表的输出
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}
	return 0;
}

以上是2种版本的算法实现