题解 P1048 【采药】

dudujerry · 2017-09-18 17:59:08 · 题解

明显01背包...

推导下状态转移方程：

有两种情况：

1.能选

2.不能选

能选又可以分为

1.选 2.不选

则状态转移方程为：

max( f [ i + 1 ] [ v ] , f [ i + 1 ] [ v - w[ i ] ] + c [ i ] )

其中 v表示当前的背包空间，w [ i ] 表示草药的时间，c [ i ] 表示草药的价值。

然后，再加一个数组记忆化搜索。（不加会爆时间啊啊啊）

下面代码实现：（原谅我的英语-.-）

#include<iostream>
#include<cmath> 
#include<cstring>
using namespace std;
int t,n,shijian[100],jiazhi[100],dp[1000][1000];
int rec(int i,int shijiana)
{
    if(dp[i][shijiana]>=0)//如果求得则直接返回
    {
        return dp[i][shijiana];
    }
    int res;
    if(i==n)
    {
        res=0;
    }
    else if(shijiana<shijian[i])//如果没空间
    {
        res=rec(i+1,shijiana);
    }
    else//能选 两种情况
    {
        res=max(rec(i+1,shijiana),rec(i+1,shijiana-shijian[i])+jiazhi[i]);
    }
    return dp[i][shijiana]=res;
}
int main()
{
    memset(dp,-1,sizeof(dp));
    cin>>t>>n;//输入
    for(int i=0;i<n;i++)
    {
        cin>>shijian[i]>>jiazhi[i];
    }
    cout<<rec(0,t);//运行函数
    return 0;
}