目录DescriptionSolutionCodeDescription一共有\(n\)个食物，每个食物有3个属性，分别为\(a,b,c\)，其中\(c\)表示做这道菜的耗时。一个食物的贡献为\(a-b\timest\)，其中\(t\)表示做完这道菜的总耗时，求在\(T\)个单位时间内，最多能产生多少贡献。Solution首先，通过\(T\)的限制，\(a-b\timest\)的贡献可以看出这是一道背包问题。我们考虑\(f_{i,j}\)表示前\(i\)个食物耗时\(j\)的时间所得贡献的最大值，而裸的背包是不用排序的，所以考虑直接DP。很快就能发现，这个做法假掉了，因为遍历到\(y\)的时候

此题乍一看是普通背包，但由于物品价值不是固定的，而是随时间(重量)而改变。因此，采取不同顺序选取一组相同物品可能产生不同价值。这种问题属于泛化背包问题，要想解决，就需要固定顺序，然后使用背包。其实找到顺序并不难，只要根据贪心策略中的相邻项交换法即可得出，若要求x在y前面，就要求c[x]b[y]b[x]还要注意：由于物品价值可以为负数，故不能简单地将dp[T]当成最终答案因此可以如下实现：structThing{ llonga,b,c; inlinebooloperator=a[i].c;j--){ dp[j]=max(dp[j],dp[j-a[i].c]+(a[i].a-j*a[i].b));

此题乍一看是普通背包，但由于物品价值不是固定的，而是随时间(重量)而改变。因此，采取不同顺序选取一组相同物品可能产生不同价值。这种问题属于泛化背包问题，要想解决，就需要固定顺序，然后使用背包。其实找到顺序并不难，只要根据贪心策略中的相邻项交换法即可得出，若要求x在y前面，就要求c[x]b[y]b[x]还要注意：由于物品价值可以为负数，故不能简单地将dp[T]当成最终答案因此可以如下实现：structThing{ llonga,b,c; inlinebooloperator=a[i].c;j--){ dp[j]=max(dp[j],dp[j-a[i].c]+(a[i].a-j*a[i].b));