A17035. 红军物资均衡分配
填空题
中等
知识点
题目描述
红军物资均衡分配
题目描述
长征途中，红军有两支纵队正在行军。后方有 n 件物资需要分配给前线部队。每件物资可以有三种分配方式：
1. 分配给第一纵队；
2. 分配给第二纵队；
3. 暂时留作战略预备。
由于运输能力有限，最多只能留 m 件物资作为预备。
为了保持两支纵队的公平，要求两支纵队获得的物资总重量必须相等。物资重量为w1, w2, ..., wn。
问：有多少种分配方式使得两支纵队获得的总重量相等，且预备物资不超过 m 件？（ ）
注意：两边都不分配，即所有物资都留作预备，也算一种方案，前提是 n <= m。
输入格式
第 1 行：两个正整数 n m，分别表示物资总数、预备上限。
第 2 行：n 个正整数 w_1, w_2, ..., w_n，表示各物资重量，空格分隔。
输出格式
输出一个整数，表示满足条件的分配方案总数。
输入样例1
3 3
1 2 3输出样例1
3输入样例2
3 1
1 2 3输出样例2
2输入样例3
4 0
2 3 5 10输出样例3
2参考答案
#include <bits/stdc++.h>
using namespace std;
int n, m;
int w[25];
long long ans = 0;
// i 表示当前处理第 i 件物资
// sum1 表示第一纵队目前获得的总重量
// sum2 表示第二纵队目前获得的总重量
// cnt 表示目前留作预备的物资数量
void dfs(int i, int sum1, int sum2, int cnt)
{
// 预备数量超过上限，直接剪枝
if (cnt > m) return;
// 所有物资都已经处理完，检查两队重量是否相等
if (i > n) {
if (sum1 == sum2) {
ans++;
}
return;
}
// 情况 1：第 i 件物资分给第一纵队
dfs(i + 1, sum1 + w[i], sum2, cnt);
// 情况 2：第 i 件物资分给第二纵队
dfs(i + 1, sum1, sum2 + w[i], cnt);
// 情况 3：第 i 件物资留作战略预备
dfs(i + 1, sum1, sum2, cnt + 1);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
// 从第 1 件物资开始搜索
dfs(1, 0, 0, 0);
cout << ans;
return 0;
}答案解析
每件物资有三种状态，直接用深度优先搜索枚举：
1. 分给第一纵队；
2. 分给第二纵队；
3. 留作预备。 搜索参数记录当前处理到第几件物资、第一纵队总重量、第二纵队总重量、预备数量。如果预备数量已经超过 m，这条分支不可能合法，直接剪枝。处理完所有物资后，如果两队总重量相等，就把答案加 1。
上一题
下一题