[动态规划]天平

2023-12-28 20:45:05

天平

题目描述

Gigel有一个奇怪的天平,他想要使它平衡。事实上,这个东西与其他普通的天平是不同的。
它有两条重量可以忽略的臂,每条臂的长度是15。臂上有一些挂钩,Gigel想要从他拥有的G个重物中(1 <= G <= 20)挂一些上去,这些重物有着不同的重量,重量范围在1到25之间。Gigel可以把任意的重物放到任意的挂钩上,但他必须全部用完所有重物。
最终,Gigel成功地利用他在全国信息学奥赛中的经验将天平弄平衡了。现在他想知道有多少种方式可以让它平衡。
挂钩的位置和重物的重量是已知的,写一个程序来计算能使天平平衡的所有可能数目。
测试样例保证至少有一种能使之平衡的方案。

关于输入

输入由以下组成:
? 第一行包含整数C(2 <= C <= 20)和整数G(2 <= G <= 20);
? 下一行包含C个整数(这些数字也是互不相同的,按递增排序),范围在-15到15之间,代表挂钩的分配;每个数字代表在X轴上相对天平中心的位置(当没有重物在天平上时,天平沿X轴方向平衡。距离的绝对值代表挂钩与天平中心的距离,数字的符号决定挂钩在哪个臂上:负号代表在左臂,正号代表在右臂)
? 再下一行是G个互不相同的自然数,按递增排序,范围在1到25之间,代表重物的重量值。

关于输出

输出包含一个数M,代表使天平平衡的可能方案个数。

例子输入
2 4
-2 3
3 4 5 8
例子输出
2
提示信息

为了与POJ中保持一致,输出结果在可以用int表示的范围内。
使用动态规划。

解题分析

注意,我们要使得天平达到平衡,并且确保每个物品都放上了,所以说,我们可以对每个物品进行枚举,他们分别可以放在不同的钩子上,当我们把全部物品放完之后,就检查一下这个时候天平是不是平衡的,如果是的话,我们就增加方案数,最后输出即可。

#include <iostream>
using namespace std;

int C,G,hook[25],weight[25],ans=0,count=0;

void dfs(int k){
    if(k==G+1){
        if(ans==0) count++;
        return;
    }
    for(int i=1;i<=C;i++){
        ans+=hook[i]*weight[k];
        dfs(k+1);
        ans-=hook[i]*weight[k];
    }
}


int main() {
    scanf("%d%d",&C,&G);
    for(int i=1;i<=C;i++)
        scanf("%d",&hook[i]);
    for(int j=1;j<=G;j++)
        scanf("%d",&weight[j]);
    dfs(1);
    printf("%d\n",count);
	return 0;
}

显然,在小数据范围内,这是有效的,然而,一旦数据达到20 * 20 我们就要枚举20的20次方次!这显然不是一个好的算法!(思路正确但是效率极其低下)。所以,我们考虑采用动态规划去完成本题。

但是我们如何利用动态规划的思想呢?在物品和挂钩有负数的情况下,我们考虑使用一个dp数组dp[i][j],表示考虑前i个物品,偏移量为j时的方法数,这就很巧妙了,我们很容易得到这样一个递推关系,dp[i][j+weight[i]*hook[m]]+=dp[i-1][j]+1,加一表示我们放了物品i,所以增加了一种方法,用+=是因为我们可以由不同的放置方法达到这个物品数和这个偏移量,所以这样去更新。

并且我们设置dp[0][BALANCE]=1(其中BALANCE我们看做一个较大的常数,用来放置数组下标为负数),表示放0件物品就平衡的方法数为1。

程序首先读取输入,包括挂钩数量C、重物数量G、挂钩位置数组hook[]和重物重量数组weight[]。

然后,定义一个二维数组dp[25][MAXSUM],其中dp[i][j]表示前i个重物放置在天平上达到平衡状态,使得天平左臂重量减去右臂重量等于j-BALANCE的方案数。BALANCE是一个偏移量,用于保证dp数组的下标不会超出范围。

接下来,程序进行动态规划的过程。首先,将dp[0][BALANCE]设置为1,表示天平上没有放置任何重物时,天平处于平衡状态。然后,遍历所有的重物,对于每个重物,遍历所有的可能状态。

对于第i个重物,如果dp[i-1][j]不为0,表示前i-1个重物放置在天平上达到偏移量为j且方法数已知,那么可以将第i个重物放置在任意一个挂钩上,使得天平左臂重量减去右臂重量的变化量为weight[i]*hook[m]。

最后,程序输出dp[G][BALANCE],即前G个重物放置在天平上达到平衡状态的方案数。

需要注意的是,为了与题目中保持一致,程序使用BALANCE偏移量来保证dp数组的下标不会超出范围,并且输出结果在可以用int表示的范围内。

代码实现
#include <iostream>
#define BALANCE 25*15*15
#define MAXSUM 2*BALANCE+10
using namespace std;

int C,G,hook[25],weight[25];
int dp[25][MAXSUM];

int main() {
	scanf("%d%d",&C,&G);
	for(int i=1;i<=C;i++){
	    scanf("%d",&hook[i]);
	}
	for(int i=1;i<=G;i++){
	    scanf("%d",&weight[i]);
	}
	dp[0][BALANCE]=1;
	for(int i=1;i<=G;i++)
	    for(int j=1;j<=MAXSUM;j++){
	        if(dp[i-1][j]){
	            for(int m=1;m<=C;m++){
	                dp[i][j+weight[i]*hook[m]]+=dp[i-1][j];
	            }
	        }
	    }
	printf("%d\n",dp[G][BALANCE]);
	return 0;
}

文章来源:https://blog.csdn.net/StudyingPanda/article/details/135276473
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。