实例参考上一篇文章。
#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;
}