首页 > 其他 > 详细

基础背包问题的一些题目!!

时间:2014-01-20 22:37:50      阅读:486      评论:0      收藏:0      [点我收藏+]

hdu1203

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1203

每件物品的cos为a[i],价值与b[i]有关,是一个简单的01背包问题。

AC代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

double dp[10005];
int a[10005];
double b[10005];

int main()
{
    int n,m,i,j;
    while(cin>>n>>m&&n+m)
    {
        for(i=0;i<m;i++)
            cin>>a[i]>>b[i];

        memset(dp,0,sizeof(dp));
        for(i=0;i<m;i++)
            for(j=n;j>=a[i];j--)
                dp[j]=max(dp[j],1-(1-dp[j-a[i]])*(1-b[i]));

        double res=dp[n]*100;
        printf("%.1f%%\n",res);
    }
    return 0;
}



hdu2602

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2602

典型的01背包,直接见代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[1002],i,j,num,vol;
int cos[1002],wei[1002];

void ZeroOnePack(int cost,int weight)
{
    for(j=vol;j>=cost;j--)
        if(dp[j]<dp[j-cost]+weight)
           dp[j]=dp[j-cost]+weight;
}

int main()
{
   int tes,n;
   cin>>tes;
   while(tes--)
   {
       cin>>n>>vol;
       for(i=0;i<n;i++)
           scanf("%d",&cos[i]);
       for(i=0;i<n;i++)
           scanf("%d",&wei[i]);
       memset(dp,0,sizeof(dp));
       for(i=0;i<n;i++)
          ZeroOnePack(wei[i],cos[i]);
       cout<<dp[vol]<<endl;
   }
   return 0;
}


hdu 1171

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1171

有n件物品,每件物品的价值和数量不同,是一个完全背包问题,由于数量并不是很大,可以将它转换为01背包问题。

AC代码:

//用两个包使得装得总量差尽量小
//就找一个总量sum/2的包看最多能装多少
//物品最多有n*m<=5000个.箱子开5000*50/2<2*10^5
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int dp[200005];
int wei[5005];

int main()
{
    int t,i,j,n,v,m,sum;
    while(cin>>t&&t>0)
    {
        n=sum=0;
        memset(dp,0,sizeof(dp));
        for(i=0;i<t;i++)
        {
            cin>>v>>m;
            sum+=v*m;
            while(m--)
                wei[n++]=v;
        }

        for(i=0;i<n;i++)
            for(j=sum/2;j>=wei[i];j--)
                dp[j]=max(dp[j],dp[j-wei[i]]+wei[i]);

        cout<<sum-dp[sum/2]<<" "<<dp[sum/2]<<endl;
    }
    return 0;
}


hdu1864

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1864

貌似是个背包问题,不过背包需要用到int,由于答案需要保留两位有效数字,所以将背包的cos放大100倍,把背包的容量也扩大一百倍,不过这样多少会有点精度的损失。01背包。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

double wei[35],dp[3000005];

int main()
{
    double sum,sa,sb,sc,money;
    int t,n,q,i,j;
    int flag;
    char c;
    while(cin>>sum>>t&&t)
    {
        n=0;
        memset(dp,0,sizeof(dp));
        while(t--)
        {
            cin>>q;
            sa=sb=sc=0;  //分别记录每张发票的A,B,C价钱
            flag=0;
            while(q--)
            {
                scanf(" %c:%lf",&c,&money);
                if(c<‘A‘||c>‘C‘||money>600)   //不可报销或单项物品金额>600
                    flag=1;
                if(c==‘A‘) sa+=money;
                else if(c==‘B‘) sb+=money;
                else if(c==‘C‘) sc+=money;
            }
            if(!flag&&sa+sb+sc<=1000&&sa<=600&&sb<=600&&sc<=600)
                wei[n++]=sa+sb+sc;
        }

        int isum=sum*100;
        for(i=0;i<n;i++)
        {
            int iwei=wei[i]*100;
            for(j=isum;j>=iwei;j--)    //同时扩大100倍
                dp[j]=max(dp[j],dp[j-iwei]+wei[i]);
        }

        printf("%.2lf\n",dp[isum]);
    }
    return 0;
}
/*
200.00 3
2 A:23.50 B:100.00
1 C:650.00
3 A:59.99 A:120.00 X:10.00
1200.00 2
2 B:600.00 A:400.00
1 C:200.50
1200.50 3
2 B:600.00 A:400.00
1 C:200.50
1 A:100.00
100.00 0
1000 4
1 A:300
1 B:300
1 A:200
1 C:500
*/

hdu1712

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1712

题目说的意思是有n个作业,如果用j天去完成第i项作业,那么会得到价值wei[i][j],因此每项任务要么不完成,要么只能完成一次,是一个完全背包的问题,可以先看下背包九讲的内容P06.

for 所有的组k

    for v=V..0

        for 所有的i属于组k

            f[v]=max{f[v],f[v-c[i]]+w[i]}

意思就是说每个组里面最多只能选一项。


AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int wei[105][105];
int dp[105];

int main()
{
    int n,m,i,j,k;
    while(cin>>n>>m&&n+m)
    {
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&wei[i][j]);

        for(i=1;i<=n;i++)   //分成的n组
            for(j=m;j>=0;j--)   //总共用j天
                for(k=1;k<=m;k++)   //所有的k属于组i
                    if(j>=k)
                        dp[j]=max(dp[j],dp[j-k]+wei[i][k]);
        cout<<dp[m]<<endl;
    }
    return 0;
}

hdu2660

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2660

题目先给你一个n,k,有n个物品,下面依次是n个物品的cos和wei,然后是背包的容量是vol,不过有个条件背包装的物品数目得不多于k,因此需要用到二维的01背包。dp[l][j]表示容量为l,最多装j个物品时候装得最大价值。状态转移方程为 dp[l][j]=max(dp[l][j],dp[l-cos[i]][j-1]+wei[i])


AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[1002][21],i,j,vol,k,l;
int cos[1002],wei[1002];

int main()
{
   int T;
   cin>>T;
   while(T--)
   {
       memset(dp,0,sizeof(dp));
       int n;
       scanf("%d%d",&n,&k);
       for(i=0;i<n;i++)
           scanf("%d%d",&wei[i],&cos[i]);
       scanf("%d",&vol);

       for(i=0;i<n;i++)
          for(l=vol;l>=cos[i];l--)
              for(j=1;j<=k;j++)
                 dp[l][j]=max(dp[l][j],dp[l-cos[i]][j-1]+wei[i]);

       printf("%d\n",dp[vol][k]);
   }
   return 0;
}



hdu1709

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1709

题目大意:给定几个数字,作为砝码,看哪些不能被称出。
解题思路:先01背包求出可以相加的所有的情况,找出可以被称出的重量,再暴力找出可以使用减法的情况。


AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[10005];
int vis[10005];
int xx[10005];
int res[10005];
int a[105],sum,n,t;

void onepack(int cost,int weight)
{
	int l;
    for(l=sum;l>=cost;l--)
		if(dp[l]<dp[l-cost]+weight)
           dp[l]=dp[l-cost]+weight;
}

int main()
{
   int i,j;
   while(~scanf("%d",&n))
   {
	  memset(dp,0,sizeof(dp));
	  memset(vis,0,sizeof(vis));
	  sum=0;
      for(i=0;i<n;i++)
	  {
		  scanf("%d",&a[i]);
		  sum+=a[i];
	  }

	  for(i=0;i<n;i++)
         onepack(a[i],a[i]);

	  for(i=1;i<=sum;i++)
		  vis[dp[i]]=1;
      //先背包求出所有和能组成的

	  t=0;
	  for(i=1;i<=sum;i++)
		  if(vis[i])
			  xx[t++]=i;
      //把背包求出的可行值都存放入xx数组中

	  for(i=0;i<t;i++)
		for(j=i+1;j<t;j++)
			vis[xx[j]-xx[i]]=1;   //用一次减法可以求出的

	  t=0;
	  for(i=1;i<=sum;i++)
          if(!vis[i])
		     res[t++]=i;
	  printf("%d\n",t);

	  if(t>0)
	  {
         for(i=0;i<t-1;i++)
			 printf("%d ",res[i]);
		 printf("%d\n",res[t-1]);
	  }
   }
   return 0;
}


poj3624

题目地址:http://poj.org/problem?id=3624

标准的01背包。。。

白天断电断网,一血也没了。。

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int dp[15000];
int cos[5000],wei[5000];

int main()
{
    int i,j,n,vol;
    while(cin>>n>>vol)
    {
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            cin>>cos[i]>>wei[i];
        for(i=0;i<n;i++)
            for(j=vol;j>=cos[i];j--)
                dp[j]=max(dp[j],dp[j-cos[i]]+wei[i]);
        cout<<dp[vol]<<endl;
    }
    return 0;
}


基础背包问题的一些题目!!

原文:http://blog.csdn.net/coraline_m/article/details/18506387

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