01背包问题

题目如下

给定一个大小为8的背包，再给4个体积分别为{2，3，4，5}的物品，他们的价值分别是{3，4，5，6}。请问，怎么样的装法使得背包可以装的价值最大？

1，暴力法解决。

顾名思义，将所有的组合列举出来，再找最大的那个就好了。说的简单，试一试能不能写出来呢?

思路：
对物品编号进行一个组合的穷举；
比如4个物品，编号1，2，3，4
组合有1 ，12，123，1234，124，13，134，14，2，23，234，24，34，4

#include
#include
using namespace std;

int volume[5] = { 0,2,3,4,5 };
int value[5] = { 0,3,4,5,6 };
int ans = 0;
int bag = 8;
int path[10];
void dfs(int pre,int sum,int mon)  //sum是当前背包装的体积，mon是当前总价值
{
	if (sum>bag||pre==5)  //如果所装物品超过背包体积，或者遍历完所有物品，输出
	{
		int temp = 0;
		for (int i = 1; i <5; i++)
		{
			if (path[i] != 0)
			{
				temp += value[i];
				printf("%d ", i);
			}
		}
		cout << endl << "价值：" << temp << endl;
		return;
	}
	for (int i = pre; i <= 4; i++)
	{
		if (sum + volume[i] <= bag)   //如果当前背包还可以装下物品
		{
			path[i] = 1;
			sum += volume[i];
			mon += value[i];
			if (mon > ans)
				ans = mon;
			dfs(i + 1,sum, mon);
			path[i] = 0;
			sum -= volume[i];
			mon -= value[i];
		}
		else   //如果装不下
		{
			dfs(i + 1,sum+value[i], mon);
		}
	}
}
int main()
{
	dfs(1,0,0);
	cout << "最大价值是:" << ans;
	return 0;
}

动态规划解决

思路：
将大问题分解成小问题，先解决小问题，然后依次解决比小问题大一点的小问题，最后解决大问题。
我们还是先模拟一下动态规划的合理性再来写代码；
💛💛
首先规定：dp[i][j]表示前i件物品在背包容量为j的情况下所能装下的最大价值。

1. 先取第一个物品（物品编号为1，2，3，4）。
   编号为1，体积为2，价值为3.
   背包容量为0的时候，dp[1][0]=0;表示前1件物品在背包容积为0的时候可以装下的最大价值是0
   背包容量为1的时候，dp[1][1]=0;表示前1件物品在背包容积为1的时候可以装下的最大价值是0
   背包容量为2，dp[1][2]=3;表示前1件物品在背包容积为2的时候可以装下的最大价值是3.
   背包容积为3，dp[1][3]此时有两种选择，(1)装物品1，不装物品1.如果装物品1，则此时背包的价值是dp[1-1][3-volume[1]]+value[1]=dp[0][1]+3=0+3.
   这里解释一下：[3-volume]表示背包预留一个空间给当前物品，dp[1-1][3-volume[i]]则表示不装当前物品的最大价值，dp[1-1][3-volume]+value[1]表示不装当前物品的最大价值加上当前物品的价值。
   (2)如果不装物品1，则价值就是dp[1][2]，和前一个容积的背包价值一一。也是3.取3和3的最大值，还是3.
   这样依次后推，每次的选择都保证dp[i][j]一定有这样的性质：dp[i][j]表示前i个编号在背包容量为j的时候的最大价值

1. dp[i][j]表示所装物品编号小于等于i，容量小于等于j，所能装的最大价值
2. volume[i]表示编号为i的物品的体积。
3. value[i]表示编号为i的物品的价值
4. object[i]表示第i件物品的编号

#include
using namespace std;
int volume[5] = { 0,2,3,4,5 };
int value[5] = { 0,3,4,5,6 };
int dp[5][10];    //dp[i][j]表示前i个编号再容积为j的背包装下的最大价值是多少
int objeck[5];   //物体编号

void Dynamic()  //用动态规划求最大价值函数（dynamic，动态规划）
{
	for(int i=0;i<5;i++)
		for(int j=0;j<9;j++)
		{
			if(j<volume[i])   //如果当前背包容量装不下i物品，则当前背包的价值等于前一个背包状态的价值
				dp[i][j]=dp[i-1][j];
			else   //如果可以装下当前物品，则需要进行一个比较
			//是装了这个物品的价值大，还是不装这个物品的价值大
			{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-volume[i]]+value[i]);
			}
		}
}

void findpath(int i,int j)   //回溯找装的物品
{
	if(i==0)
	{
		for (int i = 1; i < 5; i++)
		{
			if (objeck[i] != 0)
			{
				printf("编号%d的物品装入背包\n", i);
			}
		}
		return;
	}
	if(dp[i][j]==dp[i-1][j])
	{
		object[i]=0;
		findpath(i-1,j);
	}
	else if(dp[i][j]==dp[i-1][j-volume[i]]+value[i])
	{
		object[i]=1;
		findpath(i-1,j-volume[i]);
	}
}
int main()
{
	Dynamic();
	findpath(4,8);
	cout<<"背包价值最大为:" << endl << dp[4][8];
	return 0;
}