// 最优原则：不管前面的策略如何，此后的决策是是基于当前状态（由上一次决策产生）的最优决策。
// 当最优决策序列中包含最优决策子序列时，可建立动态规划递归方法。
//
（有些问题的递归式不一定能保证最优原则，因此在求解时有必要对它进行验证。若不能保持最优原则，则不可应用动态规划方法。）
//
在得到最优解的递归式之后，需要执行回溯以构造最优解。
// 缺点：如果不努力地去避免重复计算，递归程序的复杂性将非常可观。
//
方案：如果在递归程序中解决了重复计算问题时，复杂性将急剧下降。
//
递归方程也可用迭代方程来求解，这很自然地避免了重复计算。迭代方程虽然具有相同的复杂性，不需要附加的递归栈空间，因此更快一些。

// 15×1.cpp : Defines the entry point for the console application.

#include “stdafx.h”
#include <iostream.h>
#include <stdlib.h>
#include “dosmax.h”  // has max() and min()

// 动态规划：0-1背包问题（使用递归方法）
int p[6] = {0, 6, 3, 5, 4, 6}; // p 价值，多放置一个0，是为了让下标统一，方便理解和计算。
int w[6] = {0, 2, 2, 6, 5, 4}; // w 重量
// int x[6];
int n = 5;  // 所有物品的数量
int c = 10; // 实际最大总容量

// F函数的返回值是，当前剩为余容量为y，并且当前仍有剩余物品从i到n时，的最优解。
// i为当前检索到哪个物品的序号
int F(int i, int y)
{
   if (i == n) return (y < w[n]) ? 0 : p[n]; // 最终返回点，一次性比较搞定！
   if (y < w[i]) return F(i+1, y); //
如果y小于当前重量，那么只有一个选择：继续向下搜寻，看看能不能放下后面的物品
   //
如果y大于当前物品的重量w[i]，就有两个选择了（虽然不能当场计算出这两个选择的值，但是没关系，让它们继续往下计算就是了）：
   // 最后返回（假设当前不放入物品，y的值不变）和（假设当前放入物品，y减去当前物品的重量）的两种不同选择之后，所造成不同价值的比较结果。
  
// 在i=n之前，所有的F函数代表的临时总价值，都是悬而未决的。但是一旦i=n之后，依次返回正确的值。
   // F(i+1,y) 和 F(i+1,
y-w[i])+p[i]，它们都是i+1时候的情况，分头进行计算，相互不依赖。层次分解，就好象是一颗二叉树（中间如果y<w[i]就只有一个节点）。
  
// 最后只得出一个F的值（最优值），其余F的临时总价值，全部丢弃。
   return max(F(i+1,y), F(i+1, y-w[i])+p[i]); // 切记，返回的是物品的总价值（最大值=最优解）
}

void main(void)
{
   cout << “Optimal value is “;
   cout << F(1, c) << endl;
}

// =============================dosmax.h=====================================================

#ifndef dosmax_
#define dosmax_

template <class type>
inline type max(type a, type b)
{
   return (a > b)? a : b;
}

template <class type>
inline type min(type a, type b)
{
   return (a < b)? a : b;
}

#endif

// ==================================================================================
// 如果下标从0开始，那么只需要改碰到n的情况，因为没有w[n]和p[n]存在。但当前w[i]与p[i]不变。
int p[5] = {6, 3, 5, 4, 6}; // p 价值，多放置一个0，是为了让下标统一，方便理解和计算。
int w[5] = {2, 2, 6, 5, 4}; // w 重量
int n = 5;  // 所有物品的数量
int c = 10; // 实际最大总容量

int F(int i, int y)
{
   if (i == n-1) return (y < w[n-1]) ? 0 : p[n-1]; // cas d’arret，一次性比较搞定！
   if (y < w[i]) return F(i+1, y);
   return max(F(i+1,y), F(i+1, y-w[i])+p[i]);
}

void main(void)
{
   cout << “Optimal value is “;
   cout << F(0, c) << endl;
}