典型而传统的01背包解决办法，没有做任何的优化。
/************************************************ **文件名：百炼-2773 **Copyright (c) 2010-2020 OrdinaryCrazy **创建人：OrdinaryCrazy **日期：20170805 **描述：百炼-2773参考答案 **版本：3.0 *************************************************/ #include <stdio.h> #include <stdlib.h> struct drug { int time,cost; }; int max(int a,int b) { return a > b ? a : b; } /************************************************* 这个问题的意思是，希望我们找到这样一个药品组合 1，不能超过指定用时 2，采得药物总价值最高 这是一个典型的01背包问题 状态：药品使用情况，背包剩余容量 值：药品总价值 状态转移方程：f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i]) f[i][v]表示将前i种草药在时间v允许的情况下采集可获得的最大总价值 **************************************************/ typedef struct drug drug; drug drugs[101]; short value[101][1001]; int main() { int t,m,i,j; scanf("%d%d",&t,&m); for(i = 1;i <= m;i++) scanf("%d%d",&drugs[i].time,&drugs[i].cost); for(i=1;i<=m;i++) for(j=0;j<=t;j++) { if(j<drugs[i].time) value[i][j]=value[i-1][j]; else value[i][j]=max(value[i-1][j],value[i-1][j-drugs[i].time]+drugs[i].cost); } printf("%d\n",value[m][t]); return 0; }
在空间复杂度上进行优化，逆序递推是关键。对于j不足cost[i]的情况，f[i][j]=f[i-1][j]，就不用更改，其余的则只需考虑f[i-1][0-t]中的两种情况，保证这两种情况都不要被损坏就行。
/************************************************ **文件名：百炼-2773 **Copyright (c) 2010-2020 OrdinaryCrazy **创建人：OrdinaryCrazy **日期：20170805 **描述：百炼-2773参考答案 **版本：3.1 *************************************************/ #include <stdio.h> struct drug { int time,cost; }drugs[101]; int max(int a,int b) { return a > b ? a : b; } /************************************************* 这个问题的意思是，希望我们找到这样一个药品组合 1，不能超过指定用时 2，采得药物总价值最高 这是一个典型的01背包问题 状态：药品使用情况，背包剩余容量 值：药品总价值 状态转移方程：f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i]) f[i][v]表示将前i种草药在时间v允许的情况下采集可获得的最大总价值 这种解法的时间复杂度为O(n*v),无法优化，但空间复杂度可以由O(n*v) 降低到O(v) 用f(v)保存中间状态，当循环进行到底i轮时，f(v)表示前i个物品在v背包中的 最大总价值 **************************************************/ short value[1001]; int main() { int t,m,i,j; scanf("%d%d",&t,&m); for(i = 1;i <= m;i++) scanf("%d%d",&drugs[i].time,&drugs[i].cost); for(i = 1;i <= m;i++) for(j = t;j >= drugs[i].time;j--)//逆序枚举，保证f[i-1][j-drugs[i].time]不被破坏 value[j]=max(value[j],value[j-drugs[i].time]+drugs[i].cost); printf("%d\n",value[t]); return 0; }
