实例参考搜索法文章


#include <bits/stdc++.h>
#define MAXN 100
using namespace std;

int n, MaxValue;
int w[MAXN+1], v[MAXN+1];
int dp[MAXN+1][MAXN+1];

int main()
{
	memset(dp, 0, sizeof(dp));
	scanf("%d", &n );
	for( int i=0; i<n; i++ )
		scanf("%d%d", &w[i], &v[i] );
	scanf("%d", &MaxValue );
	// dp[i][j] 的含义为从第i个物品开始挑选总重小于j时，总价值的最大值.
	// 以下的用二重循环递推得到结果，这种方式把给定范围dp数组总所有的元素都访问了一遍
	// 与用递归记忆法搜索不同的是，搜索只访问dp的一些特定位置
	for( int i=n-1; i>=0; i-- )		// 当前位置的总价值由前一个位置的总价值得到
	{
		for( int j=0; j<=MaxValue; 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] );
		}
	}
	printf("%d\n", dp[0][MaxValue] );


	return 0;
}