题意：给你n本书，你可以把它竖着摆放，然后也可以横着摆在竖着的书上面，但不能超过竖着摆放的边缘，且不可以堆叠。问你竖着摆放的最小宽度是多少。
解题思路：dp，dp[i][j] 代表 第i个 ，用竖着摆放为 j 的书横着摆放的最小值
解题代码：
1 /************************************************************ 2 * Author : darkdream 3 * Email : darkdream1994@gmail.com 4 * Last modified : 2015-03-09 20:32 5 * Filename : 294b.cpp 6 * Description : 7 * *********************************************************/ 8 // File Name: 294b.cpp 9 // Author: darkdream 10 // Created Time: 2015年03月09日 星期一 20时04分53秒 11 12 #include<vector> 13 #include<list> 14 #include<map> 15 #include<set> 16 #include<deque> 17 #include<stack> 18 #include<bitset> 19 #include<algorithm> 20 #include<functional> 21 #include<numeric> 22 #include<utility> 23 #include<sstream> 24 #include<iostream> 25 #include<iomanip> 26 #include<cstdio> 27 #include<cmath> 28 #include<cstdlib> 29 #include<cstring> 30 #include<ctime> 31 #define LL long long 32 33 using namespace std; 34 struct node{ 35 int t , w; 36 }a[200]; 37 int dp[200][300]; 38 int main(){ 39 int n; 40 scanf("%d",&n); 41 memset(dp,-1,sizeof(dp)); 42 int total = 0 ; 43 for(int i = 1;i <= n;i ++) 44 { 45 scanf("%d %d",&a[i].t,&a[i].w); 46 total += a[i].t ; 47 } 48 dp[0][0] = 0 ; 49 int mi = 1e9 ; 50 for(int i = 1;i <= n;i ++) 51 { 52 for(int j = 0 ;j <= total;j ++) 53 { 54 dp[i][j] = dp[i-1][j]; 55 } 56 for(int j = 0 ;j <= total;j ++) 57 { 58 if(dp[i-1][j] != -1) 59 { 60 if(dp[i-1][j+a[i].t] == -1) 61 dp[i][j+a[i].t] = dp[i-1][j] + a[i].w; 62 else dp[i][j+a[i].t] = min(dp[i][j+a[i].t],dp[i-1][j] + a[i].w); 63 } 64 } 65 } 66 for(int i = 1;i <= n;i ++) 67 { 68 for(int j= 0 ;j <= total ;j ++) 69 { 70 // printf("%d ",dp[i][j]); 71 if(dp[i][j] <= total -j && dp[i][j] != -1) 72 mi = min(mi,total - j ); 73 } 74 //printf(" "); 75 76 } 77 printf("%d ",mi); 78 return 0; 79 }