实例参考上一篇文章。


#include <cstdio>
#include <algorithm>
#include <string.h>
#define MAXN 100
using namespace std;

int n, MaxWeigh;
int w[MAXN+1], v[MAXN+1];
int dp[MAXN+1][MAXN+1];	//记忆数组

int rec( int i, int j )	// 从第i个物品挑选总重小于j的部分
{
	/* 注意这里的 j 不是连续变化的 */
	if( dp[i][j] >= 0 )		//如果当前状态已经搜索过了则直接调用上次的搜索结果
		return dp[i][j];

	int res;
	if( i == n )
	{
		// 已经没有剩余的物品了
		res = 0;
	}
	else if( j <w[i] )
	{
		// 无法挑选这个物品
		res = rec( i+1, j );
	}
	else
	{
		// max函数里第一个参数是不挑选当前的物品，第二个参数是挑选当前的物品然后总重量减去
		// 当前物品的重量之后的挑选情况，再加上当前这个物品的价值。
		res = max( rec(i+1, j), rec(i+1, j-w[i]) +v[i] );
	}
	/* 注意这里的 j 不是连续变化的 */
	return dp[i][j] = res;	// 递归的过程中每个状态的返回值都会记录下来
}
int main()
{
	memset( dp, -1, sizeof(dp) );
	scanf("%d", &n );
	for( int i=0; i<n; i++ )
		scanf("%d%d", &w[i], &v[i] );
	scanf("%d", &MaxWeigh );

	printf("%d\n", rec(0, MaxWeigh) );


	return 0;
}