DP
dp [i] は、厚さを表し、dp [i] の値はその厚さで最大の幅です。
その後、総数から差し引くことができます。
貪欲法の解法もあるようですが、厚さ 1 と 2 に分ける具体的な内容は他のブログを参照してください。
/\*
\* GCA : Where is the Dp,there is the wall
\*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define VAR(a,b) decltype(b) a=(b)
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#else
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...)
#endif
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Pln() printf("\\n")
#define M 104
#define PB push\_back
#define oo (1<<29)
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define eps 1e-9
inline bool xdy(double x,double y){return x>y+eps;}
inline bool xddy(double x,double y){return x>y-eps;}
inline bool xcy(double x,double y){return x<y-eps;}
inline bool xcdy(double x,double y){return x<y+eps;}
int n;
int t\[M\];
int w\[M\];
int dp\[2\*M\];
int main() {
ios\_base::sync\_with\_stdio(0);
while(~scanf("%d",&n)){
int all=0;
for(int i=0;i<n;i++){
scanf("%d%d",&t\[i\],&w\[i\]);
all+=w\[i\];
}
for(int i=0;i<=200;i++)dp\[i\]=-oo;
dp\[0\]=0;
for(int i=0;i<n;i++){
for(int j=200;j>=t\[i\];j--){
dp\[j\]=max(dp\[j\],dp\[j-t\[i\]\]+w\[i\]);
}
}
int i;
for(i=0;i<=200;i++){
if(i>=all-dp\[i\])break;
}
printf("%d\\n",i);
}
}