huanhuan_Coder的博客

问题描述有n种物品，每种只有一个，第i个物品的体积为ViV_i，重量为WiW_i。选一些物品装到一个容量为C的背包，使得背包内物品在总体积不超过C的前提下重量尽量大，1<=n<=100，1<=ViV_i<=C<=10000，1<=Wi<=106W_i<=10^6。分析用d(i,j)表示前i个物品装进容量为j的最大重量。转移函数为d(i,j)=max{d(i+1,j),d(i+1,j-V[i]+

多段图是一种特殊的DAG，其节点可以划分成若干个阶段，每个阶段只由上一个阶段所决定。问题描述给定一个m行n列（m图1 矩阵对应的最优路线分析在这个题目中，每一列就是一个阶段，每个阶段都有3种决策：直行、右上和右下。有了前面的经验，不难设计出状态：设d(i,j)为从格子(i,j)出发到最后一列的开销。但是本题不仅要输出解，还要求字典

1、矩形嵌套问题问题描述：有n个矩形，每个矩形可以用两个整数a、b描述，表示它的长和宽，矩形X(a,b)可以嵌套在矩形Y(c,d)中，当且仅当a分析：矩形之间的可嵌套关系是一个典型的二元关系，二元关系可以用图来建模。如果矩形X可以嵌套在矩形Y中，就从X到Y连一条有向边。这个有向图是无环的，因为一个矩形无法直接或间接的嵌套在自己的内部。换句话说，它是一个DAG，我们要求的

动态规划的核心是状态和状态转移方程。问题描述与状态定义动态规划的典型问题是数字三角形问题，如上图的图1所示，有一个非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，从第一行的数开始，每次可以往左下或者右下走一格，知道走到最下行，把沿途经过的数全部加起来，如何走才能使得这个和尽量大。分析解决这个问题的时候，每次有两种选择：左下或者