Codeforce294 B. Shaass and Bookshelf（01背包）

题意：

数据范围：n<=100，1<=t[i]<=2，1<=w[i]<=100

解法：

01背包变形.
v[i]表示书的厚度,w[i]表示书的宽度.
d[i]表示将厚度为i的书放在上面(代价是宽度的和),需要的最小书架长度.
每种书对应放上面和不放上面,对应01背包的两种决策.设厚度总和为c,当厚度i放在上面时,显然c-i厚度在下面.
此时上面的宽度为d[i],那么当c-i>=d[i]时符合条件,可以用c-i更新答案.
找到合法的最小答案即可.

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=1e6;
int d[maxm];
int v[maxm];
int w[maxm];
int n;
signed main(){
    cin>>n;int c=0;for(int i=1;i<=n;i++){
    cin>>v[i]>>w[i];//v[i]是厚度,w[i]是宽度c+=v[i];}for(int i=0;i<=c;i++)d[i]=1e9;d[0]=0;for(int i=1;i<=n;i++){
    for(int j=c;j>=v[i];j--){
    d[j]=min(d[j],d[j-v[i]]+w[i]);}}int ans=1e9;for(int i=0;i<=c;i++){
    if(c-i>=d[i]){
    //c-i是书架长度ans=min(ans,c-i);}}cout<<ans<<endl;return 0;
}