动态规划算法

题目:一朵花2元,一个花瓶5元.

优惠价,3朵花不是6元而是5元,2个花瓶加一朵花10元.设计一算法,求最优解.

分析：设i为花，j为花瓶。

当i=0,j<=2时，有：f(i,j)=5j;

当i<3,j<2时，有：f(i,j)=2*i+5*j;

当i>=3,j<2时，有：f(i,j)=f(i-3,j)+5;

当0<i<3,j>=2时，有：f(i,j)=f(i-1,j-2)+10;

而当i>=3,j>=2时，则在f(i-3,j)+5及f(i-1,j-2)+10选出最小值。

代码：

#include "iostream.h"
int min(int x, int y)
{
    int z;
    z = x > y ? y : x;
    return (z);
}
int f(int i, int j)
{
    if (i < 3 && j < 2)
        return (2 * i + 5 * j);
    if (i >= 3 && j < 2)
        return (f(i - 3, j) + 5);
    if (i > 0 && i < 3 && j >= 2)
        return (f(i - 1, j - 2) + 10);
    if (i == 0 && j >= 2)
        return (5 * j);
    else
        return min((f(i - 3, j) + 5), (f(i - 1, j - 2) + 10));
}
void main()
{
    int f(int i, int j);
    int a, b;
    cout << "how many flowers do you want?" << endl;
    cin >> a;
    cout << "how many bottles do you want?" << endl;
    cin >> b;
    cout << "The money to pay:" << f(a, b) << endl;
    return;
}

结果：（如2）

2

2

12