频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu 4501 小明系列故事——买年货(多维背包)
2013-07-11 13:25:40      个评论      
收藏   我要投稿

刚开始比较容易想到小明又两种包,一种是钱,一种是积分。当时让我很纠结的是免费赠送的k件物品该怎么使用。苦思良久,拿最贵的话,因为有两种价格,这两种价格可能冲突;拿实际价值最高的吧,这个物品的标价却可能非常低,甚至是免费。这个k的使用条件让我很纠结。

当时就在想这个k的使用条件应该是什么样的,是静态的还是动态的。想到这儿突然就明白了,这个k值不就是小明的第三种背包嘛!

按说能想到这儿这道题就算做出来了,可我在写判定条件的时候脑子不知道怎么就抽筋了,我在比较的时候,是拿dp[j][k][l]分别和其他几种条件比,而不是用temp去比。当时想的是如果用temp,那么在三次比较中c[i]岂不是要加三次?

我得有多笨!

 

#include<stdio.h>
#include<string.h>
#define N 105
int dp[N][N][10];
int Max(int x,int y)
{
    if(x>y)
        return x;
    else
        return y;
}
int main()
{
    int n,v1,v2,t;
    int a[N],b[N],c[N];
    int i,j,k,l;
    while(scanf("%d%d%d%d",&n,&v1,&v2,&t)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d%d%d",&a[i],&b[i],&c[i]);
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
        {
            for(j=v1;j>=0;j--)
                for(k=v2;k>=0;k--)
                    for(l=t;l>=0;l--)
                    {
                        int temp=0;
                        if(l>0)
                            temp=Max(temp,dp[j][k][l-1]+c[i]);
                        if(k>=b[i])
                            temp=Max(temp,dp[j][k-b[i]][l]+c[i]);
                        if(j>=a[i])
                            temp=Max(temp,dp[j-a[i]][k][l]+c[i]);
                        dp[j][k][l]=Max(dp[j][k][l],temp);
                    }
        }
        printf("%d\n",dp[v1][v2][t]);
    }
    return 0;
}

 

点击复制链接 与好友分享!回本站首页
上一篇:归并排序的原理及时间复杂度
下一篇:C++零基础入门学习(cout/cin)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站