解题思路:
#include <stdio.h> //基因突变版背包问题 "人人为我"递推dp 变量名都太长了··· #define max(x,y) x>y?x:y struct { int money; int important; } things[61][3]={0,0}; //物品的基本信息 int main() { int n,maxmoney; int bag[32000]={0}; //背包 int i,j; int money,important,attchment; scanf("%d%d",&maxmoney,&n); for (i=1;i<=n;i++) { scanf("%d%d%d",&money,&important,&attchment); if (!attchment) { things[i][0].money=money; things[i][0].important=important; } else { if (!things[attchment][1].money) { things[attchment][1].money=money; things[attchment][1].important=important; } else { things[attchment][2].money=money; things[attchment][2].important=important; } } } for (i=1;i<=n;i++) { if (!things[i][0].money) //如果不是主件跳过 continue; for (j=maxmoney;j>=things[i][0].money;j--) { bag[j]=max(bag[j],bag[j-things[i][0].money]+things[i][0].money*things[i][0].important); if (j>=things[i][0].money+things[i][1].money) bag[j]=max(bag[j],bag[j-things[i][0].money-things[i][1].money]+things[i][0].money*things[i][0].important+things[i][1].money*things[i][1].important); if (j>=things[i][0].money+things[i][2].money) bag[j]=max(bag[j],bag[j-things[i][0].money-things[i][2].money]+things[i][0].money*things[i][0].important+things[i][2].money*things[i][2].important); if (j>=things[i][0].money+things[i][1].money+things[i][2].money) bag[j]=max(bag[j],bag[j-things[i][0].money-things[i][1].money-things[i][2].money]+things[i][0].money*things[i][0].important+things[i][1].money*things[i][1].important+things[i][2].money*things[i][2].important); } } printf("%d",bag[maxmoney]); return 0; }
注意事项:
参考代码:
0.0分
0 人评分
去掉双斜杠注释 (C语言代码)浏览:1825 |
点我有惊喜!你懂得!浏览:1338 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:730 |
C二级辅导-分段函数 (C语言代码)浏览:566 |
C二级辅导-统计字符 (C语言代码)浏览:541 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:735 |
C语言训练-斐波纳契数列 (C语言代码)浏览:2827 |
川哥的吩咐 (C语言代码)浏览:875 |
永远的丰碑 (C语言代码)浏览:656 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:585 |