|
|
题目：http://bjutacm.openjudge.cn/lianxi/1092/
大意：有n本书，每本书有宽度和厚度。竖着放的书m本，占书架sum(m)的长度。n-m本书横着放，其宽度和不能超过sum(m)。
这题是站长找给我的。一开始想数枚举所有书架长度并且二分，后来发现不好实现。
其实这题就是01背包问题的简单变式。
书架宽度看为背包容量
每本书的厚度看为物品重量
每本书的宽度看为物品价值
于是那个几乎在每本算法书上都有的转移方程：- f[j]=max(f[n-1][j],f[n-1][j-w]+v);
[i][i][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;
}
}
}
|
有人找乐子，有人照镜子
|
发表于 2016-12-31 22:08:36
