enjoy's Blog

- 未命名 -

Posted by enjoy

8 4, 2010

做dp题目应该特别注意状态的表示和状态转移方程。

状态d[j]：报销了前i个报销单后的报销限额为j的最大报销数

状态转移方程：d[j]=max(d[j],d[j-w[i]]+w[i]);

   for(i=0; i<m; ++i)
      for(j=Q; j>=w[i]; --j){
         if(d[j-w[i]]+w[i]>d[j]) d[j] = d[j-w[i]]+w[i];
      }//注意一维背包的应该从Q到0规划

Posted by enjoy

8 4, 2010

状态d[j]：报销了前i个报销单后的报销限额为j的最大报销数

状态转移方程：d[j]=max(d[j],d[j-w[i]]+w[i]);