有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];
}
}
这是我的代码,麻烦之指出错误。应该是在状态转移方程那里。
黄舟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数组中的下标
.
只做了最簡單的測試, 不保證程序完全正確.
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];
}