题目链接:http://poj.org/problem?id=1837
题目大意:
给你c(2<=c<=20)个挂钩,g(2<=g<=20)个砝码,求在将所有砝码(砝码重1~~25)挂到天平(天平长 -15~~15)上,并使得天平平衡的方法数
输入:
2 4 //C 钩子数 与 G钩码数
-2 3 //负数:左边的钩子距离天平中央的距离;正数:右边的钩子距离天平中央的距离c[k]
3 4 5 8 //G个重物的质量w[i]
思路:将g个挂钩挂上的极限值:15*25*20==7500
那么在有负数的情况下是-7500~~7500 以0为平衡点
那可以将平衡点往右移7500个单位,范围就是0~~15000这样就好处理多了
其实我觉得以后的题目中不仅仅天平问题可以这样处理,在有负数的以及要装入数组处理的题目中,我们都可以尝试着平移简化问题
这题目是要将所有的砝码都挂到天平上后的最多方法数,同时砝码自带质量,也就是说,这不仅仅有着“容量”的限制,还有着“件数”的限制,所以用二维费用背包
每个砝码只能用一次,果断01背包,并且在处理这一状态前,先判断前一状态是否存在 用>0表示存在,用0表示不存在,而这个题目又是求方法数,不需要再减去1
#include<iostream> using namespace std; int main() { int w[25],s[25]; //s[] 天平的座标;w[]不同重量的砝码; int dp[25][15002]={0}; int i,j,k,m,g; cin>>m>>g; for(i=1;i<=m;i++) cin>>s[i]; for(i=1;i<=g;i++) cin>>w[i]; dp[0][7500]=1; //7500为天枰达到平衡状态时的平衡度
// 放入前0个物品后,天枰达到平衡状态7500的方法有1个,就是不挂钩码
for(i=1;i<=g;i++) for(j=1;j<=15000;j++) if(dp[i-1][j]) for(k=1;k<=m;k++) dp[i][j+w[i]*s[k]]+=dp[i-1][j]; cout<<dp[g][7500]<<endl; return 0; }