CF294B 书架

Shaass拥有n本书。他想为他的所有书制作一个书架，并想让书架的长宽尽量小。
第i本书的厚度是t[i]，且这本书的纸张宽度是w[i]。书的厚度是1或2，所有书都有同样的高度（即书架的高是均匀的）
Shaass以以下的方式摆放这些书籍。

• 1.他选择了一些书并竖直摆放它们。
• 2.他将剩余的书籍水平纺织于竖直的书上面。 水平放置的书的宽度和不能多于竖直放置的书的总厚度。

帮助Shaass找到可以达到的书架长度最小值。

1. 动态规划

dp[i]定义为取厚度和为i时最小宽度和

void maxval(int n,vector<int>&c,vector<int>&w){ 
    int sum = accumulate(c.begin(),c.end(),0);
    vector<int> dp(sum+1,sum);
    dp[0] = 0;
    for(int i=0;i<n;i++)
        for(int j=sum;j>=c[i];j--)
            dp[j] = min(dp[j],dp[j-c[i]]+w[i]);
    for(int j=sum;j>=0;j--)
        if(sum-j>=dp[j]){
            cout<<sum-j;
            return;
        }
    return;
}