求解一道acm

显示全部楼层 · 2021-1-27 06:00:18

Description
上次小新开发的搜索引擎很不错,于是,就有公司找上门来,想要和他签合作合同,对于每个查询词,广告商会给一定的出价,当然,每个查询词最多只能分配给100个广告商.每个广告商也有一定的预算,超出了预算,广告商就不会付钱了.小新当然希望钱多多益善啦,这样他就能去很多地方玩了.于是,问题就来了,怎么样分配查询词,使搜网的广告收益最大化?

Input
只有一组数据.第一行有两个正整数n和m,表示n个公司,m个关键词(100 -->

千问 · 2021-1-27 06:00:18

以下是我的思路：
首先去掉“最多只能分配给100个广告商”和“每个广告商也有一定的预算”的限制。那么最后拍下来就是一个m*n的矩阵了。
1.刚好符合限制，则大功告成；
2.只有一个广告超过100个厂商，而每个广告商的预算没有超出。把投标该广告的价格排序，去掉最少的几个价格即可。如果有若干个广告超出，同样方法即可；
3.没有广告超出100个厂商，而有1个广告商超出预算，则把该广告商的投标价格排序，类同2；
4.有1个广告超出100，有一个广告商超出预算。那么就会有选择（是否去掉该广告商投标的该广告）。这两个情况（去掉和不去掉要分别算）。如果不去掉，把广告商剩下的投标和广告的投标按方法2，3处理即可（因为它们已经没有互相制约了）。如果去掉也是同理算。
5.如果有多个限制超出，可以按照4的方法找出超出的限制进行遍历。

千问 · 2021-1-27 06:00:18

以下是我的思路：
首先去掉“最多只能分配给100个广告商”和“每个广告商也有一定的预算”的限制。那么最后拍下来就是一个m*n的矩阵了。
1.刚好符合限制，则大功告成；
2.只有一个广告超过100个厂商，而每个广告商的预算没有超出。把投标该广告的价格排序，去掉最少的几个价格即可。如果有若干个广告超出，同样方法即可；
3.没有广告超出100个厂商，而有1个广告商超出预算，则把该广告商的投标价格排序，类同2；
4.有1个广告超出100，有一个广告商超出预算。那么就会有选择（是否去掉该广告商投标的该广告）。这两个情况（去掉和不去掉要分别算）。如果不去掉，把广告商剩下的投标和广告的投标按方法2，3处理即可（因为它们已经没有互相制约了）。如果去掉也是同理算。
5.如果有多个限制超出，可以按照4的方法找出超出的限制进行遍历。

千问 · 2021-1-27 06:00:18

我感觉我的方法也不是太简单，希望有人提出更好的算法。

千问 · 2021-1-27 06:00:18

这题其实是背包问题，模型：m个广告词是用于放到背包里的物品，n个广告商就是背包，在此基础上有如下限制：
（1）每个广告词的最大数量为100（2）有的广告词（物品）不能对应（放进）某些广告商（背包）。这两个限制在背包实现过程中应该不难。对于背包问题的实现，相信你做ACM的应该很了解，实在不行网上搜一下。

千问 · 2021-1-27 06:00:18

0-1整数规划的近似……最“简便”的非平凡算法是用分数规划求解然后恰当的舍入

千问 · 2021-1-27 06:00:18

引用4楼的回复:这题其实是背包问题，模型：m个广告词是用于放到背包里的物品，n个广告商就是背包，在此基础上有如下限制：
（1）每个广告词的最大数量为100（2）有的广告词（物品）不能对应（放进）某些广告商（背包）。这两个限制在背包实现过程中应该不难。对于背包问题的实现，相信你做ACM的应该很了解，实在不行网上搜一下。
我对您的做法有些疑问：
1.我觉得这个题不是0-1背包问题，因为0-1背包问题是可以用动态规划解决。而动态是要满足局部最优必然是全局最优。
2.您的目标函数必然是每个广告商的花销最多。但是每个广告商并不是独立的，因为它们之间对于同一个广告是有竞争的。