分班问题（背包问题）？

Question

有100名学生的成绩，每个班级50人，要求两个班级的平均分越接近越好，如何分配两个班级？
用C++实现。

#include <iostream>
#include <cstring>
#include <ctime>
const int N=5000;
const int M=100;
const int K=50;
int A[N+1][M+1][K+1];
int B[N+1];
int Score[M+1];
using namespace std;
int main(int argc,char **argv){
    srand(time(NULL));
    Score[0]=0;
    memset(A,0,sizeof(int)*(N+1)*(M+1)*(K+1));
    for(int i=1;i<=M;i++)
        Score[i]=rand()%41+60;

    int k=0;    
    for(int i=1;i<=M;i++){
        for(int j=0;j<=N;j++)
        if(j+Score[i]<=2500 && k<=50 &&  A[j][i][k]+Score[i]<A[j][i][k]-Score[i])
            A[j+Score[i]][i][k++]=A[j][i][k]+Score[i];
        else
            A[j][i][k]-=Score[i];
    }
}

这是我的代码，麻烦之指出错误。应该是在状态转移方程那里。

Answer 1

这不是一个标准的 背包问题, 往上面套也挺费劲. 不如就当作一般的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数组中的下标.

只做了最简单的测试, 不保证程序完全正确.

public Set<Integer> sep(int[] score){
    int N = score.length;
    int half = Arrays.stream(score).sum() / 2;
    @SuppressWarnings("unchecked")
    Set<Integer> dp[][] = new HashSet[N / 2 + 1][half + 1];
    for(int i = 0; i < half + 1; i++)
        dp[0][i] = new HashSet<>();
    for(int i = 1; i <= N / 2; i++)
        for(int k = 0; k < N; k++)
            for(int j = score[k]; j <= half; j++)
                if(dp[i - 1][j - score[k]] != null && !dp[i - 1][j - score[k]].contains(k)){
                    if(dp[i][j] == null)
                        dp[i][j] = new HashSet<>();
                    if(sum(dp[i - 1][j - score[k]]) + score[k] > sum(dp[i][j])){
                        dp[i][j].clear();
                        dp[i][j].addAll(dp[i - 1][j - score[k]]);
                        dp[i][j].add(k);
                    }
                }
    return dp[N / 2][half];
}

private int sum(Set<Integer> list) {
    int sum = 0;
    for(int n: list)
        sum += n;
    return sum;
}

@Test
public void test(){
    testBase(5, new int[]{1, 3, 4, 4});
}

@Test
public void test2(){
    testBase(7, new int[]{1, 1, 2, 3, 4, 4});
}

@Test
public void test3(){
    testBase(4, new int[]{1, 0, 2, 1, 3, 2});
}

private void testBase(int target, int[] score) {
    int sum = 0;
    for(int i: sep(score))
        sum += score[i];
    assertEquals(target, sum);
}

用一维数组节省内存的做法:

public Set<Integer> sep(int[] score){
    int N = score.length;
    int half = Arrays.stream(score).sum() / 2;
    @SuppressWarnings("unchecked")
    Set<Integer> dp[] = new HashSet[half + 1];
    for(int i = 0; i <= half; i++)
        dp[i] = new HashSet<>();
    for(int i = 1; i <= N / 2; i++)
        for(int k = 0; k < N; k++)
            for(int j = half; j >= score[k]; j--){
                if(dp[j - score[k]].contains(k))
                    continue;
                if(sum(dp[j - score[k]]) + score[k] > sum(dp[j])){
                    dp[j].clear();
                    dp[j].addAll(dp[j - score[k]]);
                    dp[j].add(k);
                }
            }
    return dp[half];
}