背包問題的動態(tài)規(guī)劃解決辦法，中，是自底向上實(shí)現(xiàn)的，這樣計(jì)算F[i][j]是可以利用已經(jīng)計(jì)算出的F[i-1][j]或F[i-1][j-W[i]],這樣雖然避免了自頂向下對子問題重復(fù)計(jì)算的問題，但是有一些值是不需要計(jì)算的，帶記憶功能的解決方案是將兩者相結(jié)合，既不用對子問題重復(fù)計(jì)算也不用計(jì)算不需要的值

/*
 *帶有記憶功能的背包問題實(shí)現(xiàn)方法，結(jié)合了自頂向下和自低至上思想
 */
#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;
}