背包问题的带记忆功能实现方法

背包问题的动态规划解决办法，中，是自底向上实现的，这样计算F[i][j]是可以利用已经计算出的F[i-1][j]或F[i-1][j-W[i]],这样虽然避免了自顶向下对子问题重复计算的问题，但是有一些值是不需要计算的，带记忆功能的解决方案是将两者相结合，既不用对子问题重复计算也不用计算不需要的值

/*
 *带有记忆功能的背包问题实现方法，结合了自顶向下和自低至上思想
 */
#include <iostream>
using namespace std;
//方便起见这里直接用定值了
int Weights[5]={0,2,1,3,2};
int Values[5]={0,12,10,20,15};
int F[5][6];
int MFKnapsack(int i,int j)
{
    if(F[i][j]<0)
    {
        int value=0;
        if(j<Weights[i])
            value=MFKnapsack(i-1,j);
        else
            value=max(MFKnapsack(i-1,j),Values[i]+MFKnapsack(i-1,j-Weights[i]));
        F[i][j]=value;
    }
    return F[i][j];
}
int main()
{
    for(int i=1;i<5;i++)
        for(int j=1;j<6;j++)
            F[i][j]=-1;

    cout<<MFKnapsack(4,5);
    return 0;
}