POJ 1837 01背包变种
题目地址在:http://poj.org/problem?id=1837
做这个题目的开始,真的还没有什么思路,即使有人说是01背包,不过依然不知道如何将问题装换成01背包的模型。
在比较经典的背包问题中,一般会有一些物品,物品用(Wi, Vi)组成,Wi表示其重量,Vi表示其价值。 然后给一个容量固定的背包,然后选择物品,达到价值最大这个目标。
1. 当物品可以分割的时候,贪心算法
2. 当物品只有一件的时候,是01背包
3. 当物品有无数件的时候,是完全背包
4. 当物品有固定件的时候,是部分背包
这个题目的描述如下:
有一个天平,天平上有若干的挂钩,给你若干的砝码,求有多少种方法,可以让天平平衡。
这个题目我读了半天才搞明白什么意思。 用图一下子就明白了。
天平上的钩子,就是红点所示的东东,而砝码就是绿色的东东。 这里可能利用到一些物理知识, 天平平衡条件应该是
∑ wi * di = ∑ wj * dj。
其中i表示左侧的组合,j表示右侧,w表示各自重量,di表示到天平中心的距离。
力矩 = 力 * 力臂,这样依据平衡状态而得到的 DP 方程如下。
DP[i] [j + weights[i-1]*armLen[k]] += DP[i-1][j];
也等价于
DP[i] [j] += DP[i-1][j - weights[i-1]*armLen[k]];
现在我们描述所有力矩的状态,dp[i][j] 表示当我们放完了第 i 个砝码的时候,力矩是 j 的所有放法数。
如果直接用 j 会出现问题,因为左力矩是负的,不过我们可以找出一个比较大的数,将所有状态 j 加上这个数,就得到一个非负数的状态。
我们这里 砝码最大 25, 钩子最远是 15, 最多有20 个砝码。可知 最大的状态应该是 [-7500, 7500], 所有我们可以将每个状态加上 7500, 将状态变成 [0, 15000].
Source CodeProblem: 1837User: hopeztmMemory: 780KTime: 47MSLanguage: C++Result: AcceptedSource Code#include <stdio.h>#include <memory.h>#define MAX_STATUS 7500#define MAX_NUM 21int armLen[MAX_NUM];int weights[MAX_NUM];int nArm, nWeight;int DP[MAX_NUM][MAX_STATUS];int main(){int i,j; while(scanf("%d%d", &nArm, &nWeight) != EOF){memset(DP, 0, sizeof(DP)); //input for( i = 0; i < nArm; i++){scanf("%d", armLen + i); }int weightSum = 0;for( i = 0; i < nWeight; i++){scanf("%d", weights + i);weightSum += weights[i];} //get max and min status IDconst int maxStatus = armLen[nArm - 1] * weightSum;const int minStatus = armLen[0] * weightSum;DP[0][MAX_STATUS] = 1; // if we put 0 weight, and the balanced is balancedfor( i = 1; i <= nWeight; i++) // for all weights{for( j = minStatus; j <= maxStatus; j++){for( int k = 0; k < nArm ; k++){DP[i][j + weights[i-1]*armLen[k] + MAX_STATUS] += DP[i-1][j + MAX_STATUS]; }}}printf("%d\n", DP[nWeight][MAX_STATUS]);}return 0;}