|
题目:http://bjutacm.openjudge.cn/lianxi/1092/
大意:有n本书,每本书有宽度和厚度。竖着放的书m本,占书架sum(m)的长度。n-m本书横着放,其宽度和不能超过sum(m)。
这题是站长找给我的。一开始想数枚举所有书架长度并且二分,后来发现不好实现。
其实这题就是01背包问题的简单变式。
书架宽度看为背包容量
每本书的厚度看为物品重量
每本书的宽度看为物品价值
于是那个几乎在每本算法书上都有的转移方程:- f[i][j]=max(f[n-1][j],f[n-1][j-w[i]]+v[i]);
复制代码
然后把背包的最大容量从0开始向上遍历,直到剩下书的宽度和小于等于竖着放的宽度和。
这里要注意一下:因为书的宽度只有1和2。背包最大容量要以最小宽度为单位开始遍历。不然会WA................
贴一下我的AC代码
- <i><i>#include<iostream>
- #include<stdio.h>
- #include<cstring>
- using namespace std;
- int t[201]={0},w[201]={0};
- int dp[201][201]={0};
- int n=0;
- int least=2;
- //int l=0,r=200;
- int sum=0;
- int rundp(int m)
- {
- memset(dp,0,sizeof(dp));
- for(int i=1;i<=n;i++)
- {
- for(int j=m;j>0;j--)
- {
- if(t<i><=j)
- {
- dp<i>[j]=max(dp[i-1][j],dp[i-1][j-t<i>]+w<i>);
- }
- else
- {
- dp<i>[j]=dp[i-1][j];
- }
- }
- }
- return dp[n][m];//sum_w which used
- }
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>t<i>>>w<i>;
- if(t<i><least) least=t<i>;
- sum+=w<i>;
- }
- for(int i=0;i<=sum;i=i+least)
- {
- int temp=rundp(i);
- int left=sum-temp;
- if(left<=i)
- {
- cout<<i;
- break;
- }
- }
- }
复制代码
|
|