題目大意：
有一只驢運東西，左邊有n件商品，右邊m件，由於商品的重量不是都相同的，現在為了使得驢的左右兩邊商品的差值最小，問至少需要移動幾個商品。
0<n+m<=1000
時間限制1s
題目思路：
對於每件商品有兩個選擇，左邊或右邊，我們要確定至少移動幾個商品，即至少要使幾個商品從原來的一邊換到另外一邊。
假設在最優狀態時，左邊的商品重量和為res，那麼我們要求出這個ans下，的最少商品移動次數。
到此，我們發現這類似01背包問題，只是將選和不選變為動與不動。
為什麼說是類似呢？
設dp[i][j]，表示前i個商品，左邊的重量為j時的狀態
那麼對於第i個商品，
如果原來是左邊的商品，轉移方程dp[i][j]=max(dp[i][j],dp[i-1][j+w[i]);
如果原來是右邊的商品，轉移方程dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]);
而普通的01背包問題，只涉及後者的轉移，可以用一維數組直接求解，該題需要二維。
但是，我們再看一下題目，並沒有指出商品的重量范圍，但是呢，我們不妨假設商品總和不超過1w，總之一秒內是可解的。
很幸運的是AC了。
代碼：
[cpp]
#pragma comment(linker, "/STACK:102400000,102400000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<string>
using namespace std;
#define ll long long
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n))
#define clr_all(x,c) memset(x,c,sizeof(x))
#define IT iterator
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle l+r>>1
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define eps (1e-8)
#define PI 3.1415926535897932384626433832795
#define E 2.7182818284590452353602874713527
template <class T> T _min(T a,T b){return a<b? a:b;}
template <class T> T _max(T a,T b){return a>b? a:b;}
template <class T> T _abs(T a){return a>0? a:-a;}
template <class T> T _mod(T a,T m){return a<m? (a<0? (a%m+m)%m:a):a%m;}
template <class T> T _gcd(T a,T b){while(b){T t=b;b=a%b;a=t;}return a;}
template <class T> void _swap(T &a,T &b){T t=b;b=a;a=t;}
template <class T> void getmax(T &a,T b){a= a>b? a:b;}
template <class T> void getmin(T &a,T b){a= (a!=-1 && a<b)? a:b;}
int TS,cas=1;
const int M=1000+5;
int n,m,w[M],dp[2][M*20];
int lsum,rsum,sum;
void run(){
int i,j;
m+=n,lsum=rsum=0;
for(i=1;i<=n;i++){
scanf("%d",&w[i]);
lsum+=w[i];
}
for(;i<=m;i++){
scanf("%d",&w[i]);
rsum+=w[i];
}
sum=lsum+rsum;
int now=0,pre=1;
clr_all(dp,-1);
dp[now][lsum]=0;
for(i=1;i<=m;i++){
pre=now,now^=1;
for(j=0;j<=sum;j++) dp[now][j]=dp[pre][j];
for(j=0;j<=sum;j++) if(dp[pre][j]!=-1){
if(i>n) getmin(dp[now][j+w[i]],dp[pre][j]+1);
else getmin(dp[now][j-w[i]],dp[pre][j]+1);
}
}
for(i=sum/2+1;i<=sum;i++) if(dp[now][i]!=-1) break;
for(j=sum/2;j>=0;j--) if(dp[now][j]!=-1) break;
int r;
if(dp[now][i]==-1) r=j;
else if(dp[now][j]==-1) r=i;
else{
if(_abs(sum-i-i) == _abs(sum-j-j))
r= dp[now][i]<dp[now][j]? i:j;
else
r= _abs(sum-i-i)<_abs(sum-j-j)? i:j;
}
printf("%d\n",dp[now][r]);
}
void presof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
presof();
//run();
while(~scanf("%d%d",&n,&m)) run();
//for(scanf("%d",&TS),cas=1;cas<=TS;cas++) run();
return 0;
}
#pragma comment(linker, "/STACK:102400000,102400000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<string>
using namespace std;
#define ll long long
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n))
#define clr_all(x,c) memset(x,c,sizeof(x))
#define IT iterator
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle l+r>>1
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define eps (1e-8)
#define PI 3.1415926535897932384626433832795
#define E 2.7182818284590452353602874713527
template <class T> T _min(T a,T b){return a<b? a:b;}
template <class T> T _max(T a,T b){return a>b? a:b;}
template <class T> T _abs(T a){return a>0? a:-a;}
template <class T> T _mod(T a,T m){return a<m? (a<0? (a%m+m)%m:a):a%m;}
template <class T> T _gcd(T a,T b){while(b){T t=b;b=a%b;a=t;}return a;}
template <class T> void _swap(T &a,T &b){T t=b;b=a;a=t;}
template <class T> void getmax(T &a,T b){a= a>b? a:b;}
template <class T> void getmin(T &a,T b){a= (a!=-1 && a<b)? a:b;}
int TS,cas=1;
const int M=1000+5;
int n,m,w[M],dp[2][M*20];
int lsum,rsum,sum;
void run(){
int i,j;
m+=n,lsum=rsum=0;
for(i=1;i<=n;i++){
scanf("%d",&w[i]);
lsum+=w[i];
}
for(;i<=m;i++){
scanf("%d",&w[i]);
rsum+=w[i];
}
sum=lsum+rsum;
int now=0,pre=1;
clr_all(dp,-1);
dp[now][lsum]=0;
for(i=1;i<=m;i++){
pre=now,now^=1;
for(j=0;j<=sum;j++) dp[now][j]=dp[pre][j];
for(j=0;j<=sum;j++) if(dp[pre][j]!=-1){
if(i>n) getmin(dp[now][j+w[i]],dp[pre][j]+1);
else getmin(dp[now][j-w[i]],dp[pre][j]+1);
}
}
for(i=sum/2+1;i<=sum;i++) if(dp[now][i]!=-1) break;
for(j=sum/2;j>=0;j--) if(dp[now][j]!=-1) break;
int r;
if(dp[now][i]==-1) r=j;
else if(dp[now][j]==-1) r=i;
else{
if(_abs(sum-i-i) == _abs(sum-j-j))
r= dp[now][i]<dp[now][j]? i:j;
else
r= _abs(sum-i-i)<_abs(sum-j-j)? i:j;
}
printf("%d\n",dp[now][r]);
}
void presof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
presof();
//run();
while(~scanf("%d%d",&n,&m)) run();
//for(scanf("%d",&TS),cas=1;cas<=TS;cas++) run();
return 0;
}
