D-Balance|01背包

题目链接：http://poj.org/problem?id=1837

我看到题目的时候，没什么想法，我觉得对于每个钩码来说就只有要与不要(1|0)两种关系，于是我写出了以下DP关系式：

dp[i][j]+=dp[i-1][j-a[k]*b[i]];

其中7500为这个天平的平衡点，因为任何一边的重量都小于等于这个值。

于是我将平衡点初始化为1；即DP[0][7500]=1，表示一个挂钩都不挂有一种平衡法。

以下是我的AC代码：

/*
name:Rollchuchy
type:01 Package
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAX_N 15000 /*20*25*15*2=15000*/
using namespace std;
int dp[25][MAX_N];
int main()
{//freopen("in.txt","r",stdin); int C,G;cin>>C>>G;//int le=0,ri=0;int a[25],b[25];for(int i=1;i<=C;i++){/*cin>>x;if(x<0) le+=abs(x);else ri+=x;*/cin>>a[i];}for(int i=1;i<=G;i++){cin>>b[i];}memset(dp,0,sizeof(dp));dp[0][20*25*15]=1;/*一个挂钩都不挂的平衡法有1种*/for(int i=1;i<=G;i++)/*枚举挂钩和砝码*/{for(int k=1;k<=C;k++){for(int j=a[k]*b[i];j<=MAX_N;j++)//if(j-a[k]*b[i]>=0)/*不加判断直接RE*///{//	dp[i][j]+=dp[i-1][j-a[k]*b[i]];//}dp[i][j]+=dp[i-1][j-a[k]*b[i]];}}cout<<dp[G][20*25*15]<<endl; return 0;}