//------------------------------------------------------------

对于环形的动态规划，

可以把数组下标复制一份然后进行动态规划

//------------------------------------------------------------

在动态规划的具体编程中，可能许多时候写出了正确的状态转移方程，但编写后的程序却得不到正确解，这很有可能是因为动态规划的循环的顺逆序，或者循环的内外层出现了错误。

在这里忽略其他资料中的理论知识，而具体说动态规划是如何实现的。

// 在这里的给出的全部代码都没有经过调试而直接写出

// 如果出现错误，请指出

从01背包开始说起。

稍微掌握动态规划的人都可以熟练地写出如下代码：

for(i=1;i<=n;i++)
  for(j=v;j>=c[i];j--)
    d[j]=max(d[j],d[j-c[i]]+w[i])；

一般的动态规划都是先枚举状态再枚举决策，可能初学者不明白以上的代码是怎么回事，因为这是降维之后的状态表示，降维之前的是：

d[i][j]=max(d[i-1][j],d[i-1][j-c[i]]+w[i])；

之所以可以降维是因为：观察状态转移方程，第i次的决策只与第i-1次所记录的状态有关，于是想，能不能有一种方法只用一维数组，就可以在状态转移能够正确进行？答案是肯定的，那就是第二层使用逆序循环。

NOIp 2006 金明的预算方案

先处理一下给出的物品，分成若干组，转化为分组背包问题。

写出分组背包的状态转移方程：

d[k][j]=max(d[k-1][j],d[k-1][j-c[k][i]]+w[k][i])；

对于分组背包，给出如下代码：

for 所有组k
  for j=V to 0
    for 所有物品i属于组k
      d[j]=max(d[j],d[j-c[k][i]]+w[k][i])；

// 《背包问题九讲》中的代码似乎有点错误

同样，先观察状态转移方程，还是只取决于第k-1组记录的状态，又要使每组中物品只选一件或者一件都不选。这样就确定了分组背包只能是上面的循环次序，因为只有这样在第k组决策的时候才能保证从第k-1组的状态转移而来；简单地说就是，在第二层固定了前k组物品占用的空间，那么无论选择哪一个i，最终这个状态都只能被第k组的一个物品占用；试想如果像《背包问题九讲》中那样把第二层循环和第三层循环颠倒过来，那么就有可能第k层的状态由第k层的状态转移而来，从而不能保证最多选择一件物品。

Vijos GF

二维费用的背包。

状态转移方程直接给出如下：

d[i][j][k]=max(d[i-1][j][k],d[i-1][j-c1[i]][k-c2[i]]+w[i])；

同样可以降到二维，因为是每个GF只能选择一次（题目中好像没有这么说，很久之前做的了，不太记得了，但是现实生活中的经验告诉我们每个GF只能选择一次），所以在循环枚举j和k的时候要使用逆序。

Vijos 情敌

当然可以理解为和“金明的预算方案”一样，是有依赖关系的背包问题，但是这道题却在数据的规模上告诉我们用那种方法是不可行的。更好的做法是搜索和动态规划结合，每次枚举超级情敌在第一个月消灭、第二个月消灭、第三个月消灭（即不消灭），然后对其余情敌进行动态规划。

省略搜索部分，而着重说说动态规划。

状态转移方程：

d[i][j][k]=max(d[i-1][j][k],d[i-1][j-c1[i]][k],d[i-1][j][k-c2[i]])；

由于有可能某个超级情敌没有被消灭，而在枚举i的时候枚举了这个超级情敌，如果在这时直接判断后continue，可能造成d[i]层的空缺，以至于d[i+1]层的错误。所以在处理这样可能出现某一层出现空缺的情况时，要把空缺的那一层全部从它的上一层把状态继承下来，以保证后来的状态转移的正确。

总结一下。

对于一道题目写出状态转移方程之后，程序的实现有时候是显而易见的，但有时候却又需要思考一番。这时候还是需要立足于状态转移方程，另外还要考虑到题目中的一些限制条件，设计合适的循环顺逆序和内外层。

//------------------------------------------------------------