首页 > 代码库 > 动态规划的初次接触,简单分析

动态规划的初次接触,简单分析

一、简单的0,1背包问题

1、题目描述:有n个重量和价值分别为Wi,Vi的物品。从这些物品中挑选出总重量不超过W的物品,求所选方案中价值总和的最大值(注:在0,1背包问题中,每个物品只有一件,可以选择房或者不放)。


【分析】:对于这样的问题,首先我们可以用最简单容易想到的方法,将所有可能一一例举出来,找到最合适的。


对于函数rec(int i,int j)// 这里的 i 表示的是第几个物品,而 j 表示此时背包的容量。

既然是最朴素,简单的想法,那我们就去想一想当前的这件物品我们是否要把它放入背包之中。1、如果不放入背包,我们便直接考虑下一个物品,即:rec(  i+1, j)// 此时i + 1表示下一个物品,背包的容量没有改变,仍然为j;2、如果当前的物品我们加入背包了,即:rec( i+1,j - w[ i ])+v[ i ]   // 此时才能表示这个我们所得得价值。


详见代码:

#include<iostream>
using namespace std;
// n表示物品的个数,W表示背包的容量 
int n,W;
// 数组w表示各个物品的容量,数组v表示各个物品的价值 
int w[100],v[100];

int rec(int i,int j)
{
	int res;
	// 没有剩余的物品 
	if(i == n)
	{
		res = 0;
	//  这个物品不能选择,因为大于背包的容量 
	}else if(j < w[i]){
		res = rec(i + 1,j);
	}
	//  挑选或者不挑选这个物品的情况分别尝试 
	else{
		res = max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
	}
	return res;
}

int main()
{
	cin>>n;
	for(int i = 0;i<n;i++)
	{
		cin>>w[i]>>v[i];
	}
	cin>>W;
	cout<<rec(0,W)<<endl;
	return 0;
}

由此,最简单朴素的方法,我们就解决了这个0,1背包问题,但由于上述方法可能浪费了很多的时间,下面一个优化的方法,便由此而来。


试想在上面的搜索中每一层的搜索都有两个分支,最坏需要O(2^n),但其实这些计算结果中有一些我们是已经得到了结果的,而下一次再次搜索时又再次计算,也就是说我们重复的计算了两次,所以我们可以将第一次的计算结果都存储下来,当再次遇到的时候我们可以直接使用。(积累这里的 记忆化搜索!)

详见代码:


#include<iostream>
#include<cstring>
using namespace std;
// n表示物品的个数,W表示背包的容量 
int n,W;
// 数组w表示各个物品的容量,数组v表示各个物品的价值 
int w[100],v[100];

///在此处加一个“记忆化数组”
int dp[100][100];

int rec(int i,int j)
{
	// 若已经计算过直接使用之前的计算结果 
	if(dp[i][j] >= 0)
	{
		return dp[i][j];
	}
	int res;//结果resort
	if(i == n)
	{
		res = 0;
	}else if(j<w[i])
	{
		res = rec(i+1,j);
	}else{
		res = max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
	}
	// 将结果记录在数组之中。 
	return dp[i][j] = res;
}
int main()
{
	cin>>n;
	for(int i = 0;i<n;i++)
	{
		cin>>w[i]>>v[i];
	}
	cin>>W;
	memset(dp,-1,sizeof(dp));
	cout<<rec(0,W)<<endl;
	return 0;
}

到这里,基本形成了动态规划的雏形,但我上述的代码都是用递归去进行的,下面把递归的式子换成使用数组的递推式,也就是我们经常使用的动态规划的递推关系:

dp[ i +1][ j ]  //从前 i 个物品中选出总重量不超过 j 的物品时总价值的最大值。

dp [ 0 ][ j ]  = 0

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


即:

void solve()
{
	for(int i = 0;i<n;i++){
		for(int j = 0;j<= W;j++){
			if(j<w[i]){
				dp[i+1][j] = dp[i][j];
			}else{
				dp[i+1][j] = max(dp[i][j],dp[i][j - w[i]]+v[i]);
			}
		}
	}
	cout<<dp[n][W]<<endl;
}