佚名通过本文主要向大家介绍了背包问题,01背包问题,01背包问题动态规划,背包问题动态规划,背包问题算法等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
问题：分班问题（背包问题）？
描述:
解决方案1:
描述:
有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];
}
}
这是我的代码，麻烦之指出错误。应该是在状态转移方程那里。
解决方案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];
}