解题思路:
用的是暴力求解,从给出的药草种类n中选1个,选2个,... ,选n个,满足时间不超限制的,来计算药草价值,更新并在最后输出。
上述方法时间用的较长,如果用优化算法,用最大流思想,仅供参考思想,代码用C语言表达出来,我还不会。。。
注意事项:
参考代码:#include<stdio.h>
int maxnum;
int neednum;
int answer;
int final=0;
int time;
int a[100], b[100], c[100], d[100];
void initial()//本函数的目的,将a[10]中的元素初始化为1,2,3,...10。
{
int p;
for (p = 0; p < 100; p++)
a[p] = p;
}
void put() //组合结果的计算函数
{
int k, sum = 0;
for (k = 0; k < neednum;k++)
{
sum = c[b[k]] + sum;
if (sum > time)
return;
}
answer = 0;
for (k = 0; k < neednum;k++)
answer = answer + d[b[k]];
if (answer > final)
final = answer;
}
void setnum(int star, int x) //组合函数
{
if (x == neednum)
{
put();
return;
}
if ((maxnum - star) < (neednum - x))
return;
b[x] = a[star]; //b[0],b[1],...,b[neednum]中的元素等于a[]中的元素选取
setnum(star + 1, x + 1);
setnum(star + 1, x);
}
int main()
{
int type, i, j;
initial();
scanf_s("%d%d", &time, &type);
maxnum = type;
for (i = 0; i < type; i++)
scanf_s("%d%d", &c[i], &d[i]);
for (i = 1; i <= type; i++)
{
neednum = i;
setnum(0, 0);
}
printf("%d\n", final);
return 0;
}
0.0分
0 人评分
C二级辅导-同因查找 (C++代码)(42的倍数,,所以直接递加42输出)浏览:1097 |
C语言训练-求PI* (C语言代码)(正确结果竟然是谜一样的3.141591)浏览:1301 |
C语言训练-斐波纳契数列 (C语言代码)浏览:2826 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:1229 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:558 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:720 |
小O的数字 (C语言代码)浏览:1411 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:393 |
C二级辅导-等差数列 (C语言代码)浏览:770 |
母牛的故事 (C语言代码)浏览:455 |