HDU OJ 3496 Watch The Movie【动态规划】

原题连接：http://acm.hdu.edu.cn/showproblem.php?pid=3496

题意：给n个物品，每个物品仅有一个，每个物品有代价，价值，在n个物品中选取m个物品（正好选m个，不多不少），满足总代价小于 题上给的 v，求 满足条件的最大价值，若不能满足条件输出0；

思路：二维01背包，对于二维背包01背包和一维01背包相比，多了一层循环即可。但本题 求的是 正好选m个物品，代价小于 v 的最大价值。技巧 就在于初始化的地方！！

在dp数组中要将m=0（不考虑代价vi）时的数组值 初始化为0，其余初始化为 -1；中间循环加上一个 判断（详见代码）。。

AC代码：

#include<stdio.h>
#include<string.h>
struct hello
{
    int x;
    int y;
}w[2000];
int ok[2000][2000];
int main()
{
    int a,b,c,n,m,v,ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        //memset(ok,sizeof(ok)); 
        scanf("%d%d%d",&n,&m,&v);
        for(a=0;a<n;a++)
            scanf("%d%d",&w[a].x,&w[a].y);
        for(a=0;a<=v;a++)             //初始化
        {
            for(b=0;b<=m;b++)
            {
                ok[a][b]=-1;
                if(b==0)
                        ok[a][b]=0;
            }
        }
    
        for(a=0;a<n;a++)
        {
            for(b=v;b>=w[a].x;b--)
            {
                for(c=m;c>=1;c--)
                {
                    if(ok[b-w[a].x][c-1]!=-1)  //加个判断
                        {
                            if(ok[b][c]<ok[b-w[a].x][c-1]+w[a].y)
                            {
                               ok[b][c]=ok[b-w[a].x][c-1]+w[a].y;
                            }
                    }
                }
            }
        }
        if(ok[v][m]!=-1)
            printf("%dn",ok[v][m]);
        else
            puts("0");
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!