题目描述
总公司拥有高效设备M台,准备分给下属的N个分公司。
各分公司若获得这些设备,可以为国家提供一定的盈利。
问:如何分配这M台设备才能使国家得到的盈利最大?
求出最大盈利值。
分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数M。
输入N, M和一个N * M的矩阵
矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器的盈利
输入样例
3 3
30 40 50
20 30 50
20 25 30
输出样例
70
1 1
2 1
3 1
算法1 DFS
把m个机器分配给n个公司,暴力遍历所有方案
记录分配方案,如果能更新最优解,顺便更新一下最优解的分配方案
前n - 1个公司遍历0 ~ res的所有方案
最后一个公司拿到剩下的所有机器
C语言代码
#include<stdio.h>
#define N 11
#define M 16
int a[N][M], n, m;
int cnt[N], ans;
int ans_cnt[N];
void dfs(int num, int sum, int res) //第num个公司,总盈利,剩余设备
{
if(num == n)
{
sum += a[n][res]; //把剩下的设备都分配给第n个公司
cnt[n] = res;
if(sum > ans)
{
ans = sum;
for(int i = 1; i <= n; i ++) ans_cnt[i] = cnt[i];
}
return;
}
for(int i = 0; i <= res; i ++)
{
cnt[num] = i; //给第num个公司i个设备
dfs(num + 1, sum + a[num][i], res - i);
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
scanf("%d", &a[i][j]);
dfs(1, 0, m);
printf("%d\n", ans);
for(int i = 1; i <= n; i ++) printf("%d %d\n", i, ans_cnt[i]);
return 0;
}
算法2 分组背包
把每个公司的不同分配方案看做一组不同的物品中选一种
分配给公司几个机器看做物品体积
记录方案输出方案的方法习自@墨染空 tql,%%%
C语言代码
#include<stdio.h>
#define N 20
int f[N], w[N], g[N][N];
void print(int x, int y)
{
if(x == 0) return;
int k = g[x][y];
print(x - 1, y - k);
printf("%d %d\n", x, k);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++) scanf("%d", &w[j]);
for(int j = m; j; j --)
for(int k = 1; k <= j; k ++)
{
int val = f[j - k] + w[k];
if(val > f[j])
{
f[j] = val;
g[i][j] = k;
}
}
}
printf("%d\n", f[m]);
print(n, m);
return 0;
}
太优雅了
滑稽巨巨,暴力的话这里是不是需要回溯啊(求最优方案),我加了cnt[num]=0也可以ac
有没有发现我没回溯也ac了
发现了,但是是不是加上更严谨一点,不是回溯,是还原现场
可以但是没必要
牛逼
滑稽大佬%%%
请问 这题暴力时间复杂度该怎么分析呢 或者说怎么判断暴力不会超时呢
暴力搜复杂度一般都是指数级别的,所以一般都是数据范围很小的情况下才能用,然后根据枚举方案的不同可能最坏是 $2^n$ 或者 $n!$ 或者 $n^m$等等,具体最坏是多少可以用组合数学的方法想一下能枚举到多少种不同的方案,本题方案数应该等价于求 $\sum_{i=1}^n cnt_i = m$ 的非负整数解的方案数,利用隔板法可以算出来是 $C(m + n - 1, n - 1)$,即使跑满也不会超时。
剪枝一般是能加就加,不过加了之后这个复杂度就不好算了,一般也不会很精确的去算。
好的 我明白了 我一开始分析时间复杂度的时候以为是阶乘级别的 就一直在纠结怎么可能过的问题 原来是用隔板法分析的 谢谢滑稽大佬QAQ
赞
滑稽大佬的暴力也太优美了hhh
滑稽大佬贼喜欢暴力233
_(:3」∠)_在数据范围允许的情况下还是思维难度低的算法好整hhh
滑稽大佬太强了233
为什么求方案时要从后往前推?
因为
g[i][j]
存的是给前i
个公司分配j
台机器的最优解时第i
个公司分配了几台机器。知道了
g[i][j]
就可以知道f[i][j]
是从f[i - 1][j -g[i][j]]
推出来的要求
n
个公司m
台机器时的最优解,所以要从(n, m)
往前推输出在递归之后,所以还是顺序的
谢谢啦,转移方向就是方案
哈喽,请问一下,算法
2
有个地方是不是写错了?喔,写错了,谢谢提醒
ok
所以问题来了,这道题明明可以用dp $O(n ^ 3)$,为啥不扩大数据范围呢 #滑稽
Orz 果然是我太弱了