有100名学生的成绩,每个班级50人,要求两个班级的平均分越接近越好,如何分配两个班级?
用C++实现。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
这是我的代码,麻烦之指出错误。应该是在状态转移方程那里。
黄舟2017-04-17 12:00:18
这不是一个标准的 背包问题, 往上面套也挺费劲. 不如就当作一般的dp来处理好了.
也没太看懂你的程序. 我按我的理解写了一个java的. 首先求出 所有学生的 总成绩 / 2, 设为half, 此题 即为找出50个学生, 其总成绩最接近此 half值
.
dp 表为 Set<Integer> dp[][] = new HashSet[N / 2 1][half 1]; 对每一个dp[i][j], 即选出i个学生, 其总成绩最接近j; 每一个Set包含 此 i个学生在score数组中的下标
.
只做了最简单的测试, 不保证程序完全正确.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|