学步园

算法这东西还真不好懂，感觉有些枯燥。坚持看完，认真思考，也会有所收获的。

0-1背包是动态规划的经典问题，就不叙述太多了，主要是想写点东西记录下现在的感受和思想。

注释很详细了，写完和网上的对照了下。

主函数没什么写完整，我是用调试窗口看的结果，后来也懒得加输入结果的语句了。

#include <iostream>
#define Max 100
using namespace std;
int a[Max][Max],x[Max];
int max(int a,int b)
{
	return a>b?a:b;
}
void fun(int *w,int *v,int wmax,int n)
{//w为每个物品的重量,v为价值,wmax为背包能承受的最大重量
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=wmax;j++)
		{
			if(w[i]>j)//当第i个物品的重量大于当前背包的容量
				a[i][j]=a[i-1][j];//当前的物品不放入背包中，价值和上一次的价值相同
			else
			{//放入背包或者不放入背包，取价值最大的状态
				a[i][j]=max(a[i-1][j],v[i]+a[i-1][j-w[i]]);
			}
		}
	}
	int wtemp=wmax;
	for(i=n;i>=1;i--)
	{
		if(a[i][wtemp]>a[i-1][wtemp])
		{//说明前i个元素的价值比前i-1个元素的价值要高，也就是说明第i个元素放入背包中
			x[i]=1;
			wtemp-=w[i];
		}
		else x[i]=0;
	}
}
void main()
{
//	freopen("data.txt","r",stdin);
	int n,wmax,w[Max],v[Max];
	cin>>n>>wmax;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	fun(w,v,wmax,n);
}

图片有结果。

可以看出这个情况下，最好的是选第2,3,5,6号物品装入背包。

--2013.12.10 晚21:20 心情有点失落。