问题描述
Shaass拥有n本书。他想为他的所有书制作一个书架，并想让书架的长宽尽量小。第i本书的厚度是t[i]，且这本书的纸张宽度是w[i]。书的厚度是1或2，所有书都有同样的高度（即书架的高是均匀的）。
Shaass以以下的方式摆放这些书籍。
1.他选择了一些书并竖直摆放它们。
2.他将剩余的书籍水平纺织于竖直的书上面。 水平放置的书的宽度和不能多于竖直放置的书的总厚度。图中描绘了书籍的样本排列。
帮助Shaass找到可以达到的书架长度最小值。
输入格式
输入的第一行包含一个int型的整数n（1<=n<=100）。 下面的n行分别为v[i]和w[i]，对应了书的长度和宽度（即书籍竖直放置与水平放置所占的空间）。 （1<=t[i]<=2,1<=w[i]<=100)
输出格式
一个整数，为可以达到的最小的长度。
样例输入
3
1 10
2 1
2 4
样例输出
3
题解
背包问题的变形，我们可以将一本书长度与厚度的和类比为体积，厚度类比为价值，设所有书全部竖直放置时书架的长度为总体积，我们就可以求出水平放置的书可以提供的最大贡献，再用初始总体积减去这个值就可以得到答案了
#include<bits/stdc++.h>
#define maxn 1050
using namespace std;
inline char get(){
static char buf[3000],*p1=buf,*p2=buf;
return p1==p2 && (p2=(p1=buf)+fread(buf,1,3000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
register char c=get();register int f=1,_=0;
while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
return _*f;
}
int n,start;
int t[maxn],w[maxn];//t是长 w是宽
//分割线，上面定义转化前的变量，下面定义转化后的变量//
int N,V;
int v[maxn],g[maxn];
int dp[maxn][maxn];//第i本书放在上面或者下面时最大长度
void init(){//转化
N=n;V=start;
for(register int i=1;i<=n;i++)v[i]=w[i]+t[i],g[i]=t[i];
}
int main(){
//freopen("1.txt","r",stdin);
n=read();
for(register int i=1;i<=n;i++)t[i]=read(),w[i]=read(),start+=t[i];
init();
//cout<<N<<" "<<V<<endl;
//for(register int i=1;i<=N;i++)cout<<v[i]<<" "<<g[i]<<endl;
for(register int i=1;i<=N;i++){
for(register int j=0;j<=V;j++){
if(j>=v[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+g[i]);
else dp[i][j]=dp[i-1][j];
//cout<<dp[i][j]<<endl;
//cout<<j<<" "<<v[i]<<" "<<dp[i][j]<<endl;
}
}
cout<<start-dp[N][V];
return 0;
}
