萝卜头IT论坛

了解更多
搜索
查看: 814|回复: 1
收起左侧

【算法题解】cz_vino和他的书架

[复制链接]
发表于 2016-12-31 22:08:36 | 显示全部楼层 |阅读模式
题目:http://bjutacm.openjudge.cn/lianxi/1092/
大意:有n本书,每本书有宽度和厚度。竖着放的书m本,占书架sum(m)的长度。n-m本书横着放,其宽度和不能超过sum(m)。
QQ截图20161231215853.png
这题是站长找给我的。一开始想数枚举所有书架长度并且二分,后来发现不好实现。
其实这题就是01背包问题的简单变式。
书架宽度看为背包容量
每本书的厚度看为物品重量
每本书的宽度看为物品价值
于是那个几乎在每本算法书上都有的转移方程:
  1. f[i][j]=max(f[n-1][j],f[n-1][j-w[i]]+v[i]);
复制代码


然后把背包的最大容量从0开始向上遍历,直到剩下书的宽度和小于等于竖着放的宽度和。
这里要注意一下:因为书的宽度只有1和2。背包最大容量要以最小宽度为单位开始遍历。不然会WA................
贴一下我的AC代码



  1. <i><i>#include<iostream>
  2. #include<stdio.h>
  3. #include<cstring>
  4. using namespace std;
  5. int t[201]={0},w[201]={0};
  6. int dp[201][201]={0};
  7. int n=0;
  8. int least=2;
  9. //int l=0,r=200;
  10. int sum=0;
  11. int rundp(int m)
  12. {
  13.         memset(dp,0,sizeof(dp));        
  14.         for(int i=1;i<=n;i++)
  15.         {
  16.                 for(int j=m;j>0;j--)
  17.                 {
  18.                         if(t<i><=j)
  19.                         {
  20.                                 dp<i>[j]=max(dp[i-1][j],dp[i-1][j-t<i>]+w<i>);
  21.                         }
  22.                         else
  23.                         {
  24.                                 dp<i>[j]=dp[i-1][j];
  25.                         }
  26.                 }
  27.         }
  28.         return dp[n][m];//sum_w which used  
  29. }
  30. int main()
  31. {
  32.         cin>>n;
  33.         for(int i=1;i<=n;i++)
  34.         {
  35.                 cin>>t<i>>>w<i>;
  36.                 if(t<i><least) least=t<i>;
  37.                 sum+=w<i>;
  38.         }
  39.         for(int i=0;i<=sum;i=i+least)
  40.         {
  41.                         int temp=rundp(i);
  42.                         int left=sum-temp;
  43.                         if(left<=i)
  44.                         {
  45.                                 cout<<i;
  46.                                 break;
  47.                         }
  48.         }
  49. }
复制代码

回复

使用道具 举报

发表于 2017-1-5 20:48:50 | 显示全部楼层
机智的显卡~
回复

使用道具 举报

联系站长|手机版|萝卜头IT论坛 ( 苏ICP备15050961号-1 )

GMT+8, 2018-9-24 04:16 , Processed in 0.087068 second(s), 29 queries , Gzip On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表