C++ 代码

/*动态规划：状态表示和状态计算
  用集合的方式来理解：
    f(i,j)表示顺利走完i个怪兽，花j个金币后战斗力之和的最大值
    (j选择金币而不是战斗力的原因在于选择金币时状态数量小，仅为2X50)
  找递推关系：
    f(i-1,j-p[i])+d[i](贿赂第i只怪兽)
    f(i-1,j)(不贿赂第i只怪兽，需要满足f(i-1,j)>=d[i])
  最终结果为：
    f(n,j)中满足条件的最小j
*/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long LL;
const int N=60,M=2*N;
LL d[N];//武力值
int p[N];//金币数量
LL f[N][M];


int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    { 
        cin>>d[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>p[i];
    }
    //初始化状态
    memset(f,-1,sizeof(f));
    f[0][0]=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=2*i;j++)
        {
            if(j>=p[i]&&f[i-1][j-p[i]]!=-1) //保证索引合法以及前一个状态合法
                f[i][j]=f[i-1][j-p[i]]+d[i];
            if(f[i-1][j]!=-1&&f[i-1][j]>=d[i])
                f[i][j]=max(f[i][j],f[i-1][j]);
        }
    }

    int res=0;
    for(int j=1;j<=2*n;j++)
    {
        if(f[n][j]!=-1) 
        {
            res=j;
            break;
        }

    }
    cout<<res<<endl;
    return 0;
}