华师一附中OI组

标题: dp之背包总结篇 [打印本页]

作者: diggersun 时间: 2015-11-5 15:08
标题: dp之背包总结篇
[ 本帖最后由 diggersun 于 2015-11-5 15:11 编辑 ]\n\n原帖位置 [url]http://www.cnblogs.com/ziyi--caolu/p/3234919.html[/url]
前言：背包问题在dp中可以说是经典，作为一个acmer，到现在才正式学习dp，可以说是比较失败的。我个人比较认同一点，想要做一个比较成功的acmer，dp、搜索、数学必须精练，比较遗憾的是，对我我自身而言，并没有早早的认识到这个问题，不过现在知道了，还有一年，也不算晚。还有，我建议学背包的童鞋，都看背包九讲......

作者: diggersun 时间: 2015-11-5 15:12
[ 本帖最后由 diggersun 于 2015-11-5 15:16 编辑 ]\n\ndp之01背包

01背包，做为背包中最基础的一类背包，必须要掌握好，当然我这里说的掌握好，并不是说，你横扫hdu或者poj等oj上01背包模板题就可以的，记得很久以前，刚开始做背包问题，一天在hdu水了七八道，就自以为背包就是个模板，唉，真心不知道当时的自己是有多肤浅..........

01背包的动态转移方程，背包九讲上有详细的讲解，这里不再复述，就想说下，一维的和二维的转移方程都需要深刻理解，不要觉得任何时候01背包都可以转化为1维的数组

dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+val);

dp[j]=max(dp[j],dp[j-v]+val);

此外，还想说下，01背包为什么体积要从v---0？这个问题，背包九讲上是说可以每件物品只拿一次，恩，我觉得可以自己推推，这样理解会更加深刻.......

1、UVA624（记录路径问题）

总得来说，不管是01背包还是完全背包，其动态转移每次只有两种状态在转移，就说这道题目，

dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+val[i]) 对于dp[j]来说，它只能使由两个状态中的一个转移过来的，要么取一件，要么不取，那么我们再开一个二维数组s[j]，0表示不取，1表示取，那么不取是dp[i-1][j]，取是dp[i-1][j-v]+val[i]；这样，数组s[j]就记录下了每次动态转移的方向，在递归调用，打印路径，结果就出来了，具体可以看[url]http://www.cnblogs.com/ziyi--cao[/url] ... /04/10/3012578.html

2、UVA562（平分钱币问题）

题目大意：给定n个硬币，要求将这些硬币平分以使两个人获得的钱尽量多，求两个人分到的钱最小差值。

这类问题的关键就在平衡，而就这到题目而言，01背包本身求的就是在体积小于等于sum的情况下的最大值，那么这些硬币本身既当体积又当价值，把总价值求出来/2，再套用模板......可以说比较水的平衡问题，具体看：[url]http://www.cnblogs.com/ziyi--cao[/url] ... /04/10/3012755.html

3、组成n块钱，有多少种的问题

这类题目，一般是这样描述的：给你n块钱，有m种钱币，每种钱币只能用一次，问组成n块钱有多少种方法........

对于这类题目，我更多的感受是觉得是到递推题，其实，有好多的dp都是一个递推，然后记录更新状态的过程，要组成dp[j],那么假设有一个5快的钱币，那么首先要判断dp[j-5]有没有组成，这里我比较喜欢用0表示没有这个状态，>0表示这个状态存在，那么在初始化dp数组的时候，dp[0]=1；然后套用背包模板，其动态转移方程（倒不如说递推式）为dp[j]+=dp[j-5]；

  上面是常规题目，下面为01背包的变种题：

4、poj2184（两个属性最大和，平移问题）

题意：给定两个属性,求这两个属性的和的最大值.........

思路：对于这种题目，我们可以尝试将一个属性当作容量，另一个属性当作价值，然后考虑dp.......这个题目属性还可以是负数，那么可以采取平移1000个单位，使其不存在负数问题。将第一个属性往后平移1000个单位，然后推导其动态转移方程，若是dp，代表当加入第一个属性加到i时，符合题意的第二个属性的最大值......题意是两个属性的和的最大值，那么动态转移方程必然不是dp[j]=max(dp[j],dp[j-s[0]]+s[1]），因为这个动态转移方程固然可以求出第二个属性的最大值，但别忘了题意要求第一个属性与第二个属性的和的最大值，那么，第一个属性平移了1000个单位，在考虑动态转移时，是必须要将这个考虑进去的。可以开一个a数组记录路径，然后根据题意，
动态转移方程应该为dp[j]=max(dp[j]-a[j]*1000,dp[j-s[0]]+s[1]-(a[j-s[0]]+1)*1000),一开始a数组全部赋值为0，所以需要a[j-s[0]]+1.....因为它新加入了一个值。考虑这个方程，dp数组的初始全部赋值为负无穷大，dp[0]=0。

注意一点，在历遍查找最大值的时候，dp>0,i-a*1000>0
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define maxx 1000005
int s[maxx][2],dp[maxx],a[maxx];
int main()
{
int n;
while(scanf("%d",&n)>0)
{
      int sum=0;
      for(int i=1;i<=n;i++)
      {
         scanf("%d %d",&s[0],&s[1]);
         if(s[0]<0&&s[1]<0)
         {
            i--;
            n--;
            continue;
         }
         s[0]+=1000;
         sum+=s[0];
      }
      memset(a,0,sizeof(a));
      for(int i=0;i<=sum;i++)
      dp=-maxx;
      dp[0]=0;
      for(int i=1;i<=n;i++)
      {
         for(int j=sum;j>=s[0];j--)
         if(dp[j]-a[j]*1000<dp[j-s[0]]+s[1]-(a[j-s[0]]+1)*1000)
         {
            dp[j]=dp[j-s[0]]+s[1];
            a[j]=a[j-s[0]]+1;
         }
      }
      int maxn=0;
      for(int i=1;i<=sum;i++)
      if(maxn<dp-a*1000+i&&dp>=0&&i-a*1000>=0)
      maxn=dp-a*1000+i;
      printf("%d\n",maxn);
}
return 0;
}

5、hdu2639（第k优解问题）

题意：给出一行价值，一行体积，让你在v体积的范围内找出第k大的值.......（注意，不要和它的第一题混起来，它第一行是价值，再是体积）

思路：首先dp[j]代表的是在体积为i的时候第j优解为dp[j]......那么，我们就可以这样思考，i对应体积，那么如果只是一维的dp，代表的应该是体积为i时的最大值，那么同理，dp[1]代表的是体积为i时的最大值，那么我们就可以退出两种动态，dp[m],dp[i-s[0]][m]+s[1].....然后把这两种状态开个两个数组分别保存起来，再合并出体积为i时的前k优解......依次后推，直到dp[v][k].......
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define max(x,y) x>y? x:y
typedef int ss;
ss dp[1005][100],s[1005][2];
ss a[50],b[50];
int main()
{
int text;
scanf("%d",&text);
while(text--)
{
      ss n,v,k;
      scanf("%d%d%d",&n,&v,&k);
      for(ss i=1;i<=n;i++)
      scanf("%d",&s[1]);
      for(ss i=1;i<=n;i++)
      scanf("%d",&s[0]);
      memset(dp,0,sizeof(dp));
      if(k==0)
      {
         printf("0\n");
         continue;
      }
      for(int i=1;i<=n;i++)
      {
         for(int j=v;j>=s[0];j--)
         {
            for(int m=1;m<=k;m++)
            {
                  a[m]=dp[j][m];
                  b[m]=dp[j-s[0]][m]+s[1];
            }
            int x=1,y=1,w=1;
            a[k+1]=b[k+1]=-1;  //这个地方要注意，因为有可能a或者b数组先比较完

            while(w<=k&&(x<=k||y<=k))
            {
                  if(a[x]>b[y])
                  {
                     dp[j][w]=a[x++];
                  }
                  else
                  {
                     dp[j][w]=b[y++];
                  }
                  if(w==1||dp[j][w]!=dp[j][w-1])    //这是去重.....
                  w++;
                  //printf("111\n");
            }
         }

      }

      //for(int i=1;i<=k;i++)

printf("%d\n",dp[v][k]);

}

return 0;

}

6、hdu3644（带限制的01背包）

题意：买东西，每个东西有三个特征值，p代表价格，q代表你手中钱必须不低于q才能买这个物品，v代表得到的价值。

mark：又是变种01背包，每做一个变种的，就是一种提高。。

按照q - p以由大到小的顺序排序，然后进行01背包的DP即可。

作者: diggersun 时间: 2015-11-5 15:17
[ 本帖最后由 diggersun 于 2015-11-5 15:21 编辑 ]\n\ndp之完全背包
完全背包较之01背包，唯一区别就是01背包的物品每个只能取一次，而完全背包可以取无限次dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+val[i])dp[j]=max(dp[j],dp[j-v[i]]+val[i])；
1、poj3181（高精度背包）这道题目要用到大数加法，其他的没有什么难度，当然，你的大数加法如果写的比较挫，是会超时的......2、poj1787（多重背包转化为完全背包，以及路径记录推荐）题意：有四种硬币，1分，5分，10分，25分，分别有a,b,c,d种，给出一个n分钱，要求你求出组成n分钱最多需要的硬币数量，并且输出组成它的各种硬币的数量......学到的东西：这个题目我是用两种方法做的，一个是完全背包，一个是多重背包。做完这个题目，我对背包的理解可以说上了个层次......还有记录路径的方法，反过来求出各个硬币的数量，都是我以前做的题目没有涉及到的.......要求出各个硬币有多少种，只需要记录路径，在开一个数组统计p-path[p]，为什么可以如此？很容易想到path[p]=p-v[i]如此，p-path[p]==p-(p-v[i])==v[i]，而v[i]正好是硬币的价值........这道题目令我思考到一个东西，一般的背包问题的初始值都是将dp全部赋值为0的，而在这边dp[0]==1，并且在动态转移的过程中，还限制了dp[j]>0才可以转移，与背包的模板的动态转移不同啊？为什么要这样呢？在一般的dp题目里面，有体积，价值，所要求的不是最大价值就是最小价值，而定义的dp[i][j]意义是装有i件物品，体积为j的最大值为dp[i][j]，简化为一维的dp[j]代表的是在体积为j的时候最大价值为dp[j]。仔细观察，可以发现，在dp[j-v[i]]时，dp[j]本身就可以从dp[j-v[i]]那边得到值，因为dp[j-v[i]]这个地方，它可以组成dp[j]......也就是说，它不需要去判断在dp[j-v[i]]前面是否有数可以组成dp[j-v[i]]，因此dp[j-v[i]]为不为0，不影响最终结果......而这个题目却不同，需要赋值dp[0]=1；在动态转移的时候还得保证dp[j-v[i]]>0，这是因为题意是要求组成n分钱需要的最多硬币数量，那么你要可以组成dp[n]，dp[n-v[i]]必须要可以组成，否则就会出错.......同理，这道题目原理如此，在做给出n分钱，每种钱币有a,b,c,.....种，求组成n分钱最多的种数，也是要赋值dp[0]=1的，原理是一样的........这告诫我，在做dp题目时，要仔细思考好其前后的关系，以及中间推导至最后的关系.....
3、poj2063题意：求投资k年获得最大投资，每年都选最大利息的方案进行投资k年后就可以得到最多的人民币。
注意：每一年收到的利息都可以作为下一年的本金......其实从测试数据来看，是很好看出来的......
思路：将每一年的“体积”加上利息就好，当然，数据太大，可以除以100减少时间和空间复杂度......
解题报告：[url]http://www.cnblogs.com/ziyi--caolu/p/3214100.html[/url]

dp之多重背包

1、hdu1114（水题）
2、hdu1059
题意：价值为1，2，3，4，5，6. 分别有n[1],n[2],n[3],n[4],n[5],n[6]个。求能否找到满足价值刚好是所有的一半的方案。思路：简单的多重背包，我建议多重背包都用二进制拆分优化下........ 解题报告：[url]http://www.cnblogs.com/ziyi--caolu/p/3216818.html[/url]

3、poj1217
题意：有现今cash，和n种钱币，每种钱币有ni个，价值为di，求各种钱币组成的不超过cash的最大钱数.......思路：二进制拆分转化为01背包，或者转化为完全背包都是可以的。解题报告：[url]http://www.cnblogs.com/ziyi--caolu/p/3216827.html[/url]
4、poj2392(推荐)题意：有k种石头，高为hi，在不超过ai的高度下，这种石头可以放置，有ci种这个石头，求这些石头所能放置的最高高度.........思路：以往的什么硬币种数，最大硬币数之类的，他们的硬币都已经是排好序了的，总是从小到大，但是这个题目不同，它有着最高高度的限制，那么在思考的时候，要得到最优的，那么首先就是要对ai排序......这是贪心，然后就是多重背包了........

作者: diggersun 时间: 2015-11-5 15:21
多维背包 1、hdu4501 思路：将v1,v2，k都当作一种体积，每种物品只能取一次，求max....... 反思：以前写背包，由于只有一个体积，所以习惯性的在for中，就所取的最小值限制，而在这次，因为这里导致wa了，具体是因为在多个体积限制的背包里，当这个体积小于它的最小体积时，它可以不去减它的最小体积，而是作为一种状态来传递其他体积的限制的值.......解题报告：[url]http://www.cnblogs.com/ziyi--caolu/p/3217151.html2[/url]、hdu2159解题报告：[url]http://www.cnblogs.com/ziyi--caolu/p/3222683.html3[/url]、hdu3496题意：给你n张电影门票，但一次只可以买m张，并且你最多可以看L分钟，接下来是n场电影，每一场电影a分钟，b价值，要求恰好看m场电影所得到的最大价值，要是看不到m场电影，输出0；思路：这个题目可以很明显的看出来，有两个限制条件，必须看m场电影的最大价值........其实我前面在01背包时提过，对于这样的条件，要可以看第n场电影，那么相对应的第n-1场电影必须看了，否则不能进行动态转移.......我的想法是，0代表着这场电影没有看，>0代表这场电影看了。其他的就是动态转移了，很容易得到，dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+val[i])........当然，在最开始的dp[0][0]=1，那么得到的最大值会在第m场电影里面，最大值需要减去初始值........也就是1+ View Code?123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<iostream>#include<stdio.h>#include<string.h>using namespace std;int dp[105][1005],s[105][2];int max(int x,int y){ if(x>y) return x; else return y;}int main(){ int text; scanf("%d",&text); while(text--) { int N,M,L; scanf("%d %d %d",&N,&M,&L); for(int i=1;i<=N;i++) scanf("%d %d",&s[i][0],&s[i][1]); memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=N;i++) { for(int j=M;j>=0;j--) { for(int k=L;k>=0;k--) { if(k>=s[i][0]&&j>0&&dp[j-1][k-s[i][0]]&&dp[j][k]<dp[j-1][k-s[i][0]]+s[i][1]) { dp[j][k]=dp[j-1][k-s[i][0]]+s[i][1]; } } } } int i,maxn=0; for(i=0;i<=L;i++) if(dp[M][i]>maxn) maxn=dp[M][i]; if(maxn==0) printf("0\n"); else printf("%d\n",maxn-1); } return 0;} 4、poj2576(推荐)题意：有一群sb要拔河，把这群sb分为两拨，两拨sb数只差不能大于1，输出这两拨人的体重，小的在前面......思路：把总人数除2，总重量除2，之后你会发现就是个简单的二维背包，有两个限制.....一个是人数，一个是体重，再仔细思考下，发现一定要有这么多人，也就是说一定要有总人数除以2这么多人，那么当第n个人存在，第n-1个人必须存在.........+ View Code?1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include<iostream>#include<stdio.h>#include<string.h>using namespace std;int dp[55][23000],a[105];int main(){ int n; while(scanf("%d",&n)>0) { int m=(n+1)/2,sum=0,maxx=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum+=a[i]; } if(n==1) { printf("0 %d\n",a[1]); continue; } memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=sum/2;k>=0;k--) { if(j>0&&k-a[i]>=0&&dp[j-1][k-a[i]]&&dp[j][k]<dp[j-1][k-a[i]]+a[i]) dp[j][k]=dp[j-1][k-a[i]]+a[i]; //printf("%d\n",dp[j][k]-1); if(maxx<dp[j][k]) maxx=dp[j][k]; } } } maxx--; //printf("%d\n",maxx); int tmp=sum-maxx; if(tmp<maxx) { int h=tmp; tmp=maxx; maxx=h; } printf("%d %d\n",maxx,tmp); } return 0;} 5、poj1837（天平问题推荐）题意：给你c（2<=c<=20）个挂钩，g（2<=g<=20）个砝码，求在将所有砝码（砝码重1~~25）挂到天平(天平长 -15~~15)上，并使得天平平衡的方法数.......思路：（这是我木有想到的）将g个挂钩挂上的极限值：15*25*20==7500那么在有负数的情况下是-7500~~7500 以0为平衡点......那可以将平衡点往右移7500个单位，范围就是0~~15000......这样就好处理多了其实我觉得以后的题目中不仅仅天平问题可以这样处理，在有负数的以及要装入数组处理的题目中，我们都可以尝试着平移简化问题......这题目是要将所有的砝码都挂到天平上后的最多方法数，同时砝码自带质量，也就是说，这不仅仅有着“容量”的限制，还有着“件数”的限制，很明显的二维费用背包......每个砝码只能用一次，果断01背包，并且在处理这一状态前，先判断前一状态是否存在......我喜欢用>0表示存在，用0表示不存在，而这个题目又是求方法数，不需要再减去1........

作者: hr567 时间: 2015-11-6 13:56
沙发…………

欢迎光临华师一附中OI组 (http://hsyit.cn/)