poj 1837 Balance （dp背包）

題目大意：

有一個天平，天平左右兩邊的手臂長度都是15，手臂上面有些位置會有掛鉤。還有G個砝碼 (1 <= G <= 20)，它們重量各不相同，在1~25中取值。

給出C個掛鉤，它們的位置在【-15..15】，不會重疊。負號的代表在左邊臂，正號的在右邊。

要求把所有砝碼都放在掛鉤上，多個砝碼可以掛在同一個掛鉤上，問有多少種不同的方案使天平能夠平衡？

思路：

天平左臂的力矩和是負數，右邊的力矩和是正數，那麼左邊+右邊的力矩之和，如果是正數，代表天平平衡傾向右邊，負數代表傾向左邊，為0的時候天平是平衡的。我們把 “左邊力矩和+右邊力矩和”叫做平衡系數

狀態f[i][j]代表用前i個砝碼，放置成平衡系數為j的時候共有多少種方案。
那麼，f[i][j] += f[i-1][j-C[k]*G[i]],  {0<=k=<c};

因為平衡系數中有負數的，所以要所有平衡系數往右平移，即加上一個足夠大的正數。可以計算出力矩之和最小負數的是把所有砝碼都掛在天平-15的位置上，砝碼最多20個，取值最大的情況是6...25，那麼砝碼之和最終為 (6+25)*20/2 = 310, 力矩之和為 -15*310 = 4650
所以加上4650即可，這是位置4650代表的是原來天平的中間位置，
初始化 f[0][4650] = 1, 表示一個砝碼都不掛，這是一種平衡的方案。

最終，f[G][4650]就是答案。

PS： 這題最開始我是用滾動數組做的，用G++提交一直RE到死，郁悶。後來改用C++提交就可以AC了。

代碼：

[cpp]  #include<iostream>  
#include<cstdio>  
#include<cmath>  
#include<algorithm>  
#include<cstring>  
#define SQ(x) ((x)*(x))  
#define MP make_pair  
const int INF = 0x3f3f3f3f; 
const double PI = acos(-1.0); 
typedef long long int64; 
using namespace std; 
 
const int MAXN = 22; 
const int mid = 4650; 
int pos[MAXN], w[MAXN]; 
int f[22][mid*2+10]; 
int n, m; 
 
int main(){ 
    while(~scanf("%d%d", &n, &m)){ 
 
        for(int i=0; i<n; ++i) 
            scanf("%d", &pos[i]); 
 
        for(int i=0; i<m; ++i) 
            scanf("%d", &w[i]); 
 
        memset(f, 0, sizeof(f)); 
        f[0][mid] = 1; 
 
        for(int i=0; i<m; ++i){ 
            for(int j=0; j<n; ++j){ 
 
                int add = w[i]*pos[j];   
                for(int v=mid*2; v-add>=0; --v){   
                    if(v-add <= mid*2) 
                        f[i+1][v] += f[i][v-add]; 
                } 
            } 
        } 
        printf("%d\n", f[m][mid]); 
    } 
    return 0; 
} 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define SQ(x) ((x)*(x))
#define MP make_pair
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef long long int64;
using namespace std;

const int MAXN = 22;
const int mid = 4650;
int pos[MAXN], w[MAXN];
int f[22][mid*2+10];
int n, m;

int main(){
    while(~scanf("%d%d", &n, &m)){

        for(int i=0; i<n; ++i)
            scanf("%d", &pos[i]);

        for(int i=0; i<m; ++i)
            scanf("%d", &w[i]);

        memset(f, 0, sizeof(f));
        f[0][mid] = 1;

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){

                int add = w[i]*pos[j]; 
                for(int v=mid*2; v-add>=0; --v){ 
                    if(v-add <= mid*2)
                        f[i+1][v] += f[i][v-add];
                }
            }
        }
        printf("%d\n", f[m][mid]);
    }
    return 0;
}