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

这个显卡不太冷

题目：http://bjutacm.openjudge.cn/lianxi/1092/
大意：有n本书，每本书有宽度和厚度。竖着放的书m本，占书架sum(m)的长度。n-m本书横着放，其宽度和不能超过sum(m)。

这题是站长找给我的。一开始想数枚举所有书架长度并且二分，后来发现不好实现。
其实这题就是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. }

复制代码

nkc3g4

机智的显卡~