本文主要是介绍poj 1837 Balance 二维费用背包,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:
给你c(2<=c<=20)个挂钩,g(2<=g<=20)个砝码,求在将所有砝码(砝码重1~~25)挂到天平(天平长 -15~~15)上,并使得天平平衡的方法数.......
思路:(这是我木有想到的)将g个挂钩挂上的极限值:15*25*20==7500
那么在有负数的情况下是-7500~~7500 以0为平衡点......
那可以将平衡点往右移7500个单位,范围就是0~~15000......这样就好处理多了
其实我觉得以后的题目中不仅仅天平问题可以这样处理,在有负数的以及要装入数组处理的题目中,我们都可以尝试着平移简化问题......
这题目是要将所有的砝码都挂到天平上后的最多方法数,同时砝码自带质量,也就是说,这不仅仅有着“容量”的限制,还有着“件数”的限制,很明显的二维费用背包......
每个砝码只能用一次,果断01背包,并且在处理这一状态前,先判断前一状态是否存在......我喜欢用>0表示存在,用0表示不存在,而这个题目又是求方法数,不需要再减去1......
下面是我让10为平衡位置对样例做的输出
其实就是模拟的天平每次输入一个 秤砣然后进行更新dp,里面出现的1是当输入某一个时候分别和对应的钩子后为平衡位置的点。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[25][16005],c[25],w[25];
int main()
{int n,m;while(~scanf("%d %d",&n,&m)){for(int i=1; i<=n; i++)scanf("%d",&c[i]);for(int i=1; i<=m; i++)scanf("%d",&w[i]);memset(dp,0,sizeof(dp));dp[0][7500]=1;for(int i=1; i<=m; i++)for(int j=15000; j>0; j--)for(int k=1; k<=n; k++){if(j+w[i]*c[k]>=0&&j+w[i]*c[k]<=15000&&dp[i-1][j+w[i]*c[k]])//这一句纯属优化,没有也能对,这句的目的是减轻呢些无用的0之间互相加dp[i][j]+=dp[i-1][j+w[i]*c[k]];}printf("%d\n",dp[m][7500]);/*for(int i=0;i<=m;i++){for(int j=0;j<40;j++)printf("%d",dp[i][j]);printf("\n");}*/}return 0;
}
这篇关于poj 1837 Balance 二维费用背包的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!