admin 管理员组

文章数量: 1184232

P2392 kkksc03考前临时抱佛脚( 贪心（划掉）,dp,01背包 ,思维)

Sloution

!!!写这道题目前，先思考一个问题：

把一堆数据，分成两组，让这两组的最大值最小

如何求解?

如果是简单贪心的话，只考虑局部，比如，让当前选择
下达到最小，对于2,3,4这组数据
我们会分成2,4 和 3 。但这不是最优的。

局部最小 ！=整体最小
（很多时候，局部最小的贪心，是简单的线性结构，
而不是这样的二选一 （二选一可以用dp去写,这题可以dp,但也可以直接 去推导） ）

从整体出发：
想一下，会发现，要让两组数据差不多（偏移量小）
的情况下，最小，那么，要让大的的小的放一起，
中间大的放一起（小学思维）
但是…处理起来还是比较困难的，对于多种情况

dp:
关键在于01背包模型的建立
在容量sum/2的情况下，尽可能多的装v
（讲问题转换，01背包的建模）

int len[5];
int a[500];
int sum;
int f[2000];
int ans;
int main(){
//freopen("in.txt", "r", stdin);_for(i, 0, 4) cin >> len[i];_for(i,0,4){sum = 0;_for(j,0,len[i]){ cin >> a[j];sum += a[j];}int re = 0;int k = (sum + 1) >> 1;_for(j,0,len[i]){if(len[i]==1){re = a[j];break;}for_(x, k, a[j]) f[x] = max(f[x], f[x - a[j]]+a[j]);}re = max(f[k], sum - f[k]);//cout << " kkk " <<sum<<"    "<< f[k] << endl;ms(f, 0);//cout << re << endl;ans += re;}cout << ans;
}

本文标签： P2392 kkksc03考前临时抱佛脚( 贪心（划掉） DP 01背包 思维)

版权声明：本文标题：P2392 kkksc03考前临时抱佛脚( 贪心（划掉）,dp,01背包 ,思维) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700273898a374891.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。