POJ 1837 Balance 【01背包】

题意：有一个天平，坐标值均为【-15，15】的整数，给n个整数位置，可以悬挂砝码；给m个砝码的重量

要求：m个砝码放上天平，位置在n个中的任意一个地方，使得天平保持平衡

求总方案数目

样例：

2 4
-2 3
3 4 5 8

3*（3+5）=2*（8+4）

所以方案数目为2

思路：

n个位置，m个砝码，是肯定需要枚举一遍怎么放的：那么肯定就是dp的思路

那么，如果定义我们的dp【i】【j】呢？

想到背包：i是放完了前几个物品，j是当前的体积：那么，同理：i是放完了几个砝码，j怎么处理？

天平保持平衡：意味着枚举完毕之后，最后停在了0：因为题目中有负数，我们需要进行偏移：

最大重量25，挂在-15的位置，最多20个，所以乘起来，最小负数是-7500！所以我们往右偏移7500（意味着数组大小是15000的）

那么：dp【i】【j】就定义好了：放完了前i个砝码，当前的天平平衡值为j的数目值

最终要求的答案是dp【m】【7500】（因为m个砝码必须都放上去）

那么转移就完全跟01背包一样了：

如果当前状态有的话，那么把该砝码放进去来改变天平的平衡值

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<cstring>
using namespace std;

const int maxn=50;
const int maxm=50;

int n,m;
int a[maxn];
int b[maxm];
int dp[maxn][20050];

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(dp,0,sizeof(dp));dp[0][10000]=1;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=m;i++) scanf("%d",&b[i]);
        for(int i=1;i<=m;i++)
            for(int j=0;j<=20000;j++)
                if (dp[i-1][j])
                    for(int k=1;k<=n;k++)
                        dp[i][j+b[i]*a[k]]+=dp[i-1][j];
        printf("%d\n",dp[m][10000]);
    }
    return 0;
}