搜索

首页  >  问答  >  正文

c++ - 分班问题(背包问题)?

有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

<code>#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];

    }

}

</code>

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

高洛峰高洛峰2820 天前571

全部回复(1)我来回复

  • 黄舟

    黄舟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

    <code>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);

    }

    </code>

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

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    <code>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];

    }

    </code>

    回复
    0
  • 取消回复