解题思路:
#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语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:659 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:969 |
C语言训练-角谷猜想 (C++代码)(3N+1问题)浏览:1750 |
时间转换 (Java代码)浏览:574 |
拆分位数 (C语言代码)浏览:1327 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:866 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:765 |
简单的a+b (C语言代码)浏览:525 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:660 |
2^k进制数 (C语言描述,蓝桥杯)浏览:1420 |