首页 > 其他 > 详细

hihocoder1043 完全背包 完全背包的几种写法

时间:2015-05-26 16:10:09      阅读:154      评论:0      收藏:0      [点我收藏+]

题目链接:

hiho1043










二维:

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 505
using namespace std;
int dp[505][100005];
int need[505];
int value[505];
int main()
{
    int n,v;
    while(~scanf("%d%d",&n,&v))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            scanf("%d%d",&need[i],&value[i]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=v;j++)
            {
                int maxvalue=dp[i-1][j];
                for(int k=0;k*need[i]<=j;k++)
                {
                    int thevalue=dp[i-1][j-need[i]*k]+value[i]*k;
                    if(thevalue>maxvalue)
                        maxvalue=thevalue;
                }
                dp[i][j]=maxvalue;
            }
            printf("%d\n",dp[n][v]);
    }
    return 0;
}




一维:

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 505
using namespace std;
int dp[100005];
int need[505];
int value[505];
int main()
{
    int n,v;
    while(~scanf("%d%d",&n,&v))
    {
        int ans=0;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            scanf("%d%d",&need[i],&value[i]);
        for(int i=1;i<=n;i++)
            for(int j=0;j<=v;j++)
                for(int k=0;k*need[i]<=j;k++){
                dp[j]=max(dp[j],dp[j-need[i]*k]+value[i]*k);
                if(dp[j]>ans)
                    ans=dp[j];
            }
            printf("%d\n",ans);
    }
    return 0;
}



0-1一维:

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 505
using namespace std;
int dp[100005];
int need[505];
int value[505];
int main()
{
    int n,v;
    while(~scanf("%d%d",&n,&v))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            scanf("%d%d",&need[i],&value[i]);
        for(int i=1;i<=n;i++)
            for(int j=need[i];j<=v;j++)          //取同一物品时从前往后推
                dp[j]=max(dp[j],dp[j-need[i]]+value[i]);
            printf("%d\n",dp[v]);
    }
    return 0;
}


hihocoder1043 完全背包 完全背包的几种写法

原文:http://blog.csdn.net/axuan_k/article/details/46008159

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!