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