算法问题(二)–动态规划之01背包问题

背包问题算是动态规划问题中的经典了。

背包问题可以这样理解:

自顶向下的寻找最优解,自底向上的求解最优解。

例如:

物品个数n=5,物品重量w[n]={2,2,6,5,4},物品价值V[n]={6,3,5,4,6},背包的最大重量是10

那么在放置最后一个物品(前4个物品都已经决定了)的时候,有两种状态:放,不放。

这个时候就可以比较得出,这最后一个物品是放进背包的价值大,还是不放进背包的价值大。

同理,在放置倒数第二个物品的时候,也可以得知,是将这个物品放进去的价值更大,还是不放使得背包的价值更大。

以此类推。在第一个物品放置的时候,可以显而易见的看出,是将第一个物品放入的价值更大。

 

如果需要求解最优值的时候:

就从第一个物品开始计算,

第一个物品放入背包,那么背包的价值就是:第一个物品的价值+当背包除去第一个物品以外重量可以得到的价值

第二个物品放入背包,那么背包的价值就是:第二个物品的价值+当背包除去第二个物品以外重量可以得到的价值

……

依次类推,可以得出最优值。

如果不是很了解,可以看一下图示:

背包问题

有两则关于背包问题写得非常好的博客:
[dm href=’http://www.cnblogs.com/sdjl/articles/1274312.html’]金矿讲解背包问题[/dm][dm href=’http://blog.csdn.net/dapengbusi/article/details/7463968′]建表详讲背包问题[/dm]
仔细阅读之后,背包问题应该不成问题。

背包问题源码:

//背包问题
//2015年11月9日 23:15:42

#include <iostream>
using namespace std;

int max(int,int);
int main()
{
	cout<<"请输入物品的个数:";
	int n;
	cin>>n;
	cout<<"请输入物品的重量:";
	int *weight = new int[n+1];
	int *value = new int[n+1];
	for(int i = 1; i <= n; i++)
		cin>>weight[i];
	weight[0]=0;
	cout<<"请输入物品的价值:";
	for(int i = 1; i <= n; i++)
		cin>>value[i];
	value[0]=0;

	cout<<"请输入背包的容量:";
	int t;
	cin>>t;
	int **best = new int*[n+2];
	//best 7行,11列
	for(int i = 0; i <= (n+1); i++)
		best[i] = new int[t+1];

	for(int i=0; i<=(n+1); i++)
		for(int j=0; j<=t; j++)
			best[i][j] = 0;
	
	for(int i=5; i>=1; i--)
		for(int j=1; j<=10; j++)
			if(weight[i]>j)
				best[i][j] = best[i+1][j];
			else
				best[i][j] = max(value[i]+best[i+1][j-weight[i]], best[i+1][j]);

	
	cout<<best[1][t]<<endl;
	cin.get();
	return 0;
}


int max(int put, int noPut)
{
	if(put > noPut)
		return put;
	else
		return noPut;
}

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部