HDU2159_二维完全背包问题

输入有：经验，忍耐度，怪物种数，限制杀怪数每一种怪物对应获得的经验值和消耗的耐久值

输出：剩下的最大忍耐度

限制：忍耐度，杀怪个数

在这里把忍耐度看成背包的容量，杀怪个数限制作为第二维

dp[i][j]表示在背包容量为i的时候，放了j件物品所产生的价值

接下来就是循环问题

先遍历每一个物品（怪物） i

　　然后遍历体积（耐久值）正序遍历——完全背包 j

　　　　然后遍历杀怪的个数（正序遍历）完全背包 k

　　　　　　得出dp[j][k] = max(dp[j][k],dp[j-cost[i]][k-1] + data[i]);

　　　　　　在这里要记录一下，要保留最大的耐久值，我们就要存储，当dp[j][k]所产生的经验值大于等于升级所需要的经验值时小号的最小耐久值

最后一减就ok了

#include <iostream>

#include <cstdio>

#include <string.h>

#include <cmath>

#define inf 0xffffff

using namespace std;

const int maxn = 200;

int dp[maxn][maxn];//dp[i][j]表示忍耐度为i的情况下杀j个怪兽所获得的经验

int data[maxn];

int cost[maxn];

int main()

{

    int e,V,n,limit;

    while(~scanf("%d%d%d%d",&e,&V,&n,&limit))

    {

        for(int i = 0;i < n;i++)

            scanf("%d %d",&data[i],&cost[i]);

        memset(dp,0,sizeof(dp));

        int res = inf;

        for(int i = 0;i < n;i++)//遍历物品

            for(int j = cost[i];j <= V;j++)//完全背包层层递推

                for(int k = 1;k <= limit;k++)//不管当前这只，管当前这只

                {

                    dp[j][k] = max(dp[j][k],dp[j-cost[i]][k-1] + data[i]);

                    if(dp[j][k] >= e)res = min(res,j);

                }

        if(res == inf)cout<<-1<<endl;

        else cout<<V - res<<endl;

    }

    return 0;

}

秒客网

HDU2159_二维完全背包问题

相关文章