算法分析-选修问题（bp求解）

学校开设了n门选修课程，每门课程的学分为ci，每个学生可选课程的数量不超过m门，学生选修了这些课程并考核通过后就能获得相应的学分，在选修课程中，有些课程可以直接选修，有些课程有一门直接先修课。
你的任务是为自己确定一个选课方案，在满足先修课优先的原则下，使得你能得到的学分最多，并判断该学分有没有达到最低学分的要求，假定课程之间不存在时间上的冲突。

需要设计动态规划算法的状态转移方程，保证满足最优化原理，能正确求解最大选修学分，并输出。

测试输入：
10,6 //一共十门课，挑选六门
3,1,2,5,2,4,4,1,5,2 //1~10选修课的学分
1,2 //先修课， 第X个主修课，第一门和第七门选修课没有先选课存在，没有输入。
1,3
1,4
3,5
3,6
7,8
7,9
7,10
预期输出：
最大学分:23

img


这是相应解释，必须按照这个输入格式，进行输出，两列代表含义与正常题不同。

输入应该是这样描述的吧：输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中1≤N≤300,1≤M≤N。 以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。
代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 310;
int n, m;
int w[maxn], fa[maxn];
int tot, to[maxn], head[maxn], nxt[maxn];
int dp[maxn][maxn];//dp[i][j]表示以i为根的子树中选j门课的最大学分
void add(int x, int y)
{
    to[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
void dfs(int x)
{
    for (int i = head[x]; i; i = nxt[i])
    {
        int y = to[i];
        dfs(y);
        for (int j = m + 1; j >= 1; j--)
            for (int k = 0; k < j; k++)
                dp[x][j] = max(dp[x][j], dp[x][j - k] + dp[y][k]);
    }
}
int main()
{
    printf("请输入n、m:");
    scanf("%d,%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d,%d", &fa[i], &w[i]);
        add(fa[i], i);
        dp[i][1] = w[i];
    }
    dfs(0);
    printf("%d", dp[0][m + 1]);
    return 0;
}

测试样例：

img

可以帮你解答额，看到请回一下。

可以使用java语言实现吗？


using namespace std;
void menu() //主菜单
{
cout<<endl;
cout<<setw(14)<<’ ‘<<"欢迎使用学生选课系统 "<<endl;
cout<<setw(10)<<’ '<<"* * * * * * * * * * * * * * * * \n";//输出提示性信息
cout<<setw(12)<<’ ‘<<“请选择要进行的操作:\n”;//输出提示性信息
cout<<setw(18)<<’ ‘<<" 1—信息录入 "<<endl;
cout<<setw(18)<<’ ‘<<" 2—信息浏览 "<<endl;
cout<<setw(18)<<’ ‘<<" 3—选择课程 "<<endl;
cout<<setw(18)<<’ ‘<<" 4—删除信息 "<<endl;
cout<<setw(18)<<’ ‘<<" 5—修改信息 "<<endl;
cout<<setw(18)<<’ ‘<<" 6—退出程序 "<<endl;
cout<<setw(10)<<’ '<<" * * * * * * * * * * * * * * * *\n";//输出提示性信息
}
class student //学生类
{
public:
double xuehao; //学号
char name[100]; //姓名
char major[100]; //专业
char coursename[100];//学生所选课程名
void set() //学生信息录入,通过set()函数给学生类赋值
{

student stu; //定义类的对象stu
cout<<endl;
cout<<"请输入学生学号: ";
cin>>stu.xuehao;
cout<<"请输入学生姓名: ";
cin>>stu.name;
cout<<"请输入学生专业: ";
cin>>stu.major;
ofstream out("studentInfo.text",ios::app|ios::binary);//用于studentInfo.text的输出，并且文件以二进制方式操作和在文件尾部添加数据
out.write((char *)(&stu),sizeof(stu));  //对二进制文件(studentInfo.text)进行写操作（起始地址，读取或者写入的字节数）
out.close(); //关闭文件
menu();//返回主菜单 
1
2
3
4
5
6
7
8
9
10
11
12
}
void checkstudent() //查询学生信息
{
student stu;//用于临时保存学生信息的变量
cout<<“学生学号\t学生姓名\t所学专业”<<endl;
ifstream is(“studentInfo.text”,ios::binary); //创建输入流对象is
while(!is.peek())//判断文件
{
is.read((char *)(& stu),sizeof(stu)); //对二进制文件(学生.text)进行读操作
cout<<""<<stu.xuehao<<"\t\t"<<stu.name<<"\t\t"<<stu.major<<"\t\t"<<endl;
}
is.close();
menu();
}

void cancleStudent() //删除学生信息
{
string xueHaoNum,line,xuehao; //定义变量
ifstream fin(“studentInfo.text.text”); //建立ifstream的对象fin与文件"studentInfo.text.text"相关联
fstream outfile(“studentInfo.text.text”,ios::trunc|ios::out); //用于selectCourseResult.text文件的输出，打开一个文件进行写操作和使同名文件被删除
cout<<endl;
cout<<“请输入您要删除学生的学号: “;
cin>>xueHaoNum;
while(!fin.eof()) //文件不结束，执行循环体
{
getline(fin,line);
istringstream stream(line); //串流输入
xueHaoNum = line.substr(0,line.find(””,0));//复制子字符串
if(xuehao != xueHaoNum)
outfile<<line<<endl;//向outfile输出流中输出line
}
outfile.close();
fin.close();
fstream f(“studentInfo.text”,ios::trunc|ios::out); //打开一个文件进行写操作和使同名文件被删除
ifstream outf(“studentInfo.text”); //用于selectCourseResult.text文件的输入
f<<outf.rdbuf();//输出整个文件的内容
outf.close();
f.close();
cout<<endl;
menu();
}

void changestudent() //修改学生信息
{
student stu;
int mark;
cout<<endl;
cout<<"请输入需要修改信息的学生学号 ";
double xuehao;
cin>>xuehao;
ifstream is(“studentInfo.text”,ios::binary); //用于选课.text文件的输入
for(int i=0;!is.eof();i++)
{
is.seekg(48*i); //对输入文件定位，第一个参数是偏移量，第二个参数是基地址
is.read((char )(&stu),sizeof(stu)); //对二进制文件(学生.text)进行读操作
if(stu.xuehao==xuehao)
{
cout<<"请输入要修改的学生姓名 ";
cin>>stu.name;
cout<<"请输入要修改的学生专业 ";
cin>>stu.major;
cout<<“修改完毕!”<<endl<<endl;
mark=48i;
menu();
break;
}
}
is.close();
if(stu.xuehao!=xuehao)
{
cout<<“没有这个学生!”<<endl<<endl;
menu();
}
else
{
ofstream os(“studentInfo.text”,ios::in|ios::binary); //用于选课.text的输出，并且文件进行读操作和二进制方式打开
os.seekp(mark);//移动文件指针的标记
os.write((char *)(&stu),sizeof(stu)); //对二进制文件(学生.text)进行写操作
os.close();
}
}
};

class course //课程类
{
public:
double coursenum; //课程编码
char coursename[50];
char coursetapy[50];
double xuefen;
double xueshi;
char courseteacher[50];
void set() //课程信息录入， 通过set()函数给课程类赋值
{
course cus; //作为临时的课程信息保存
cout<<"请输入课程编码: ";
cin>>cus.coursenum;
cout<<"请输入课程名称: ";
cin>>cus.coursename;
cout<<"请输入课程类型: ";
cin>>cus.coursetapy;
cout<<"请输入课程学分: ";
cin>>cus.xuefen;
cout<<“请输入课程学时: “;
cin>>cus.xueshi;
cout<<“请输入主讲教师: “;
cin>>cus.courseteacher;
ofstream os(“courses.text”,ios::binary|ios::app);//将课程保存在“courses.txt”文件中
os.write((char )(&cus),sizeof(cus)); //对二进制文件(课程.text)进行写操作
os.close(); //文件(课程.text)的关闭
menu();
}
void checkcourse() //浏览课程信息
{
cout<<endl;
ifstream is(“courses.text”,ios::binary); //用于课程.text文件的输入
cout<<“课程编码 课程名称 课程类型 课程学分 课程学时 主讲教师”<<endl;
course cus;//临时保存课程信息
while(!is.peek()) //检测文件结束
{
is.read((char)(&cus),sizeof(cus)); //对二进制文件(courses.text)进行读操作
cout<<””<<cus.coursenum<<”\t “<<cus.coursename<<”\t “<<cus.coursetapy<<”\t “<<cus.xuefen<<”\t “<<cus.xueshi<<””<<cus.courseteacher<<endl; //setw()是控制输入的宽度
}
is.close();
menu();
}
void canclecourse() //删除课程信息
{
string coursenum,line,course;
ifstream fin(“courses.text”); //用于courses.text文件的输入
fstream outfile(“courses.text”,ios::trunc|ios::out);// 打开一个文件进行写操作和使同名文件被删除
cout<<endl;
cout<<“请输入您要删除课程的编码: “;
cin>>coursenum;
while(!fin.eof()) //文件不结束，继续循环
{
getline(fin,line);
istringstream stream(line); //串流输入
coursenum = line.substr(0,line.find(””,0));
if(course != coursenum)
outfile<<line<<endl;
}
outfile.close();
fin.close();
fstream f(“courses.text”,ios::trunc|ios::out); //用于courses.text文件的输出，打开一个文件进行写操作和使同名文件被删除
ifstream outf(“courses.text”); //用于学courses.text文件的输入
f<<outf.rdbuf();//输出整个文件的内容
outf.close();
f.close();
cout<<endl;
menu();
}
void changecourse() //修改课程信息
{
course cus;
int mark;//标记
cout<<endl;
cout<<"请输入要修改课程信息的编码 ";
double coursenum;
cin>>coursenum;
ifstream is(“courses.text”,ios::binary); //用于课程.text文件的输入
for(int i=0;!is.eof();i++)
{
is.seekg(28*i); //对输入文件定位，第一个参数是偏移量，第二个参数是基地址
is.read((char )(& cus),sizeof(cus)); //对二进制文件(课程.text)进行读操作
if(cus.coursenum==coursenum)
{
cout<<"请输入要修改的课程名称 ";
cin>>cus.coursename;
cout<<"请输入要修改的课程类型 ";
cin>>cus.coursetapy;
cout<<"请输入要修改的课程学分 ";
cin>>cus.xuefen;
cout<<"请输入要修改的课程学时 ";
cin>>cus.xueshi;
cout<<"请输入要修改的主讲教师 ";
cin>>cus.courseteacher;
cout<<“修改完毕!”<<endl<<endl;
mark=28i;
menu();
break;
}
}
is.close();
if(cus.coursenum!=coursenum)
{
cout<<“没有这门课程!”<<endl<<endl;
menu();
}
else
{
ofstream os(“courses.text”,ios::in|ios::binary); //用于课程.text的输出，并且文件进行读操作和二进制方式打开
os.seekp(mark);//移动文件指针的标记
os.write((char *)(& cus),sizeof(cus)); //对二进制文件(学生.text)进行写操作
os.close();
}
}
};
void selectCoures()//选课函数
{
student stu;//用于保存将要选课的那名同学的信息
int countCoures=0;//用来统计该学生选了多少门课程
int countStudent=0;//用来统计学生的个数
loop://循环结构
cout<<endl<<"请输入你的学生学号： ";
double m_xuehao,m_coursenum;//利用学号和课程号分别找出哪位同学选了哪门课
cin>>m_xuehao;
ifstream is(“studentInfo.text”,ios::binary);
is.seekg(0,ios::beg);//从文件头开始，文件指针向前移动
while(!is.peek())//判断文件结束
{
is.read((char *)(&stu),sizeof(stu)); //从"studentInfo.text"文件中一次读取学生的信息
if(m_xuehao == stu.xuehao)
{
loob:
countStudent++;
cout<<“请输入学号为”<<m_xuehao<<"的学生想要选择的课程编码(1001-9999): ";
cin>>m_coursenum;
ifstream inCourse(“courses.text”,ios::binary); //用于从"courses.text"文件中找出该同学想选择的课程信息
inCourse.seekg(0,ios::beg);从文件头开始，文件指针向前移动
while(!inCourse.eof())//选课核心代码
{
course cus;//用于此同学将要选择的课程信息
inCourse.read((char *)(&cus),sizeof(cus));// (char *)(&cus)起始地址，sizeof(cus)读取的字节数
if(m_coursenum == cus.coursenum)
{//若找到那门课程则选它
countCoures++;
strcpy(stu.coursename,cus.coursename);
ofstream outStu(“selectCourseResult.text”,ios::binary|ios::app);//现将选课的同学信息放入选课结果的文件中
outStu.write((char *)(&stu),sizeof(stu));//写入的字节数
outStu.close();
cout<<“学号为”<<m_xuehao<<“成功选了课程号为”<<m_coursenum<<“的课程!”<<endl;
}
if(countCoures>2)
{
cout<<“同学：你选择的课程已经超过”<<countCoures<<“门了!”<<endl;
break;
}
}
if(countCoures == 0)
{
cout<<“没有这门课程,还要继续选择其他课程吗y/n?”<<endl;
char ch;
cin>>ch;
if((‘y’==ch)||('Y’ch))
goto loob;
else
break;
}
inCourse.close();
}
}
if(countStudent0)
{
cout<<“没有这个学生,是否重新输入y/n?”<<endl;
char ch;
cin>>ch;
if((‘y’==ch)||(‘Y’==ch))
goto loop;
}
is.close();
menu();
}

void scanResult()//查询选课结果
{
student stu;//用于保存将要选课的那名同学的信息
cout<<“学生学号\t学生姓名\t所学专业\t选课名称”<<endl;
ifstream is(“selectCourseResult.text”,ios::binary);
for(int i=0;!is.peek();i++)
{
is.read((char*)(&stu),sizeof(stu));//对二进制文件(selectCourseResult.text)进行读操作
cout<<stu.xuehao<<"\t\t"<<stu.name<<"\t\t"<<stu.major<<"\t\t"<<stu.coursename<<endl;
}
is.close();
menu();
}

void set() //信息录入菜单
{
cout<<endl;
cout<<"﹌﹌﹌﹌﹌﹌1. 录入学生信息﹌﹌﹌﹌﹌﹌"<<endl;
cout<<"﹌﹌﹌﹌﹌﹌2. 录入课程信息﹌﹌﹌﹌﹌﹌"<<endl;
cout<<"﹌﹌﹌﹌﹌﹌3. 返回前面菜单﹌﹌﹌﹌﹌﹌"<<endl<<endl;
student stu;
course cus;
int choose;
cout<<"请输入选项序号: ";
cin>>choose;
switch(choose)
{
case 1: stu.set();break; //录入学生信息函数
case 2: cus.set();break; //录入课程信息函数
case 3: menu();break;
default: cout<<“没有这个选项,请重新输入,谢谢!”<<endl;
set();
break;
}
}

void check() //查询信息
{
cout<<endl;
cout<<"﹌﹌﹌﹌﹌﹌1. 查询学生信息﹌﹌﹌﹌﹌﹌"<<endl;
cout<<"﹌﹌﹌﹌﹌﹌2. 查询课程信息﹌﹌﹌﹌﹌﹌"<<endl;
cout<<"﹌﹌﹌﹌﹌﹌3. 查询学生选课结果信息﹌﹌﹌﹌﹌﹌"<<endl;
cout<<"﹌﹌﹌﹌﹌﹌4. 返回主要菜单﹌﹌﹌﹌﹌﹌"<<endl<<endl;
cout<<"请输入选项序号 ";
int choose;
cin>>choose;
student stu;
course cus;
switch(choose)
{

case 1: stu.checkstudent();break;  //查询学生信息函数
case 2: cus.checkcourse();break; //查询课程信息函数
case 3: scanResult();break;  //查询学生选课结果信息
case 4: menu();break;
}
1
2
3
4
5
}

void cancle() //删除信息
{
cout<<endl;
cout<<"﹌﹌﹌﹌﹌﹌1. 删除学生信息﹌﹌﹌﹌﹌﹌"<<endl;
cout<<"﹌﹌﹌﹌﹌﹌2. 删除课程信息﹌﹌﹌﹌﹌﹌"<<endl;
cout<<"﹌﹌﹌﹌﹌﹌3. 返回主要菜单﹌﹌﹌﹌﹌﹌"<<endl<<endl;
cout<<“请输入选项序号 “;
student stu;
course cus;
int choose;
cin>>choose;
switch(choose)
{
case 1: stu.cancleStudent();break; //删除学生信息函数
case 2: cus.canclecourse();break; //删除课程信息函数
case 3: menu();break;
default: cout<<“没有这个选项,请重新输入,谢谢!”<<endl;
break;
}
}
void change() //修改信息
{
cout<<endl;
cout<<”﹌﹌﹌﹌﹌﹌1. 修改学生信息﹌﹌﹌﹌﹌﹌”<<endl;
cout<<"﹌﹌﹌﹌﹌﹌2. 修改课程信息﹌﹌﹌﹌﹌﹌"<<endl;
cout<<"﹌﹌﹌﹌﹌﹌3. 返回主要菜单﹌﹌﹌﹌﹌﹌"<<endl<<endl;
cout<<"请输入选项序号 ";
student stu;
course cus;
int choose;
cin>>choose;
switch(choose)
{
case 1: stu.changestudent();break; //修改学生信息函数
case 2: cus.changecourse();break; //修改课程信息函数
case 3: cout<<endl;menu();break;
default: cout<<“没有这个选项,请重新输入,谢谢!”<<endl;
change();
}
}
int main() //主函数
{
menu();
do
{
cout<<endl<<"请输入所选择的菜单项序号: ";
int choose;
cin>>choose;
switch(choose)
{
case 1: set();break; //信息录入
case 2: check();break; //信息浏览
case 3: selectCoures();break; //选择课程
case 4: cancle();break;//删除信息
case 5: change();break; //修改信息
case 6: exit(1);
}
}while(1);
return 0;
}