Python中的动态编程任务

Question

这是我试图解决的DP问题的玩具版本.假设我们有两个社区,分别有2个和3个停车站.

1. 每个停车站的容量范围从0到固定的正数.
2. 在任何给定时刻系统的状态是站的可用停车位.例如,(2,3,4,5,6)其中(2,3)指的是第一邻域中的站点的可用点和第二邻域中的(4,5,6).
3. 每个站可以打开(1)或关闭(0),我们希望找到在每个状态下打开或关闭的站.为此,我们必须测试所有可能的开/关组合.上述设置的一个这样的组合将是[[0,1],[1,0,1]].
4. 最后,从出发社区的每个车站到目的地社区旅行都有积极的可能性.例如,λ_{1,2} ^ {2}是从邻域1中的站2到邻域2的概率.

我需要帮助的是如何存储上述内容以使生活更轻松以及如何编写状态值的计算.您可以从当前状态转换到的状态取决于lambdas概率和给定的建议.例如,对于状态(2,3,4,5,6)和建议[[0,1],[1,0,1]],值将为:

• 第一个术语的解释:鉴于这个lambda,我们得知汽车从1号街区的1号站出发去了2号街区.因此,邻域1中的站1的状态从2变为3.此外,我们在邻域2中有两个推荐站,其中汽车可以同样地去.因此,我们得到两个学期.在第一个中,邻域2中的站1的容量下降1,而在第二个项中,邻域2中的站3的容量下降1.
  • 对于第二个术语的类似解释,唯一的区别是汽车现在从1号街区的2号站出发.
  • 对于第三个学期,我们从lambda看到汽车从附近2的1号车站到1号附近.但是现在,只推荐附近1号的第2站,因此我们只得到一个站点2的容量邻域1减1,邻域2的1号减1.
  • 对其他术语的类似解释.

我脑海中存在的问题的一般伪代码:

 Create State_Space
 Create recommendation_combinations # All possible (0,1) combinations 
 V = dict([state,0] for state in State_Space) # Initialize the value vector

for each_state in State_Space:
   for each_recommendation_combination in recommendation_combinations:
       Compute V(state)_combination

   V(state) = min(V(state)_combination)

鉴于问题结构的复杂性(即社区内的站点),您如何建议存储上述内容？(我当时想要使用字典,但我不知道如何使用带字典的itertools来创建推荐组合).此外,任何编程帮助国家的价值计算非常感谢!

提前谢谢了.