动态规划算法和c++实现 国王与金矿问题

金矿问题"/>

动态规划算法和c++实现 国王与金矿问题

这个链接讲解动态规划通俗易懂：

动态规划：动态规划主要考虑到了全局最优解，第i个解与第1~i-1个解都有关

求解动态规划的过程必须考虑三个问题：1.状态转移（就是上一个状态怎么转移到下一个状态） 2.边界值  3.最优子结构

而贪心算法则是当前最优解，当前的状态只与前一个状态有关。

// ConsoleApplication5.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<math.h>
using namespace std;
//金矿数N 
//工人数W
//黄金数 G[]
//金矿用人数p[]

int max(int a, int b)
{
    return (a > b ? a : b);
}
int getMaxValue(int p[5], int n, int w, int G[5])
{
    
    int *preResult= new int[10];//前面一行的数值
    int *Result = new int[10];
    //填充第一行的数字和边缘的数字0
    for (int i = 0; i <n; i++)
    {
        if (i+1 < p[0])
        {
            preResult[i] = 0;
        }
        else
        {
            preResult[i] = G[0];
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <w; j++)
        {
        
            if (j < p[i])//工人数小于需要挖此矿的工人
            {
                Result[j] = preResult[j];
            }
            else
            {
                Result[j] = max(preResult[j],preResult[j-p[i]]+G[i]);
            }
            
        }
        for (int i = 0; i < w; i++)
        {
            cout << Result[i]<<" ";
            preResult[i] = Result[i];//计算完一行计算下一行 结果变成上一行的结果
            //cout << preResult[i];
        }
        cout << endl;
        
    }
    return Result[w-1];
}

int main()
{
    int p[5] = { 5,5,3,4,3 };
    int Result;
    int n = 5;
    int w = 10;
    int G[5] ={400,500,200,300,350};
    Result =getMaxValue(p, n, w, G);
    cout << Result;
    system("pause");
}

2.

// ConsoleApplication6.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;

int maxVolume(int n)
{
    if (n < 2)
    {
        return 0;
    }
    if (n == 2)
    {
        return 1;
    }
    if (n == 3)
    {
        return 2;
    }
    int Volume;
    int h[50] = { 0 };
    h[1] = 1;
    h[2] = 2;
    h[3] = 3;
    for (int i = 4; i < n + 1; i++)
    {
        int max = 0;
        for (int j = 1; j < (i + 1) / 2; j++)
        {
            int Volume = h[j] * h[i-j];
            if (max < Volume)
            {
                max = Volume;
            }    
        }
        h[i] = max;
    }
    return h[n];
   
}
int main()
{
    int n = 8;
    int max=maxVolume(n);
    cout << max;
    system("pause");
}

3.

// ConsoleApplication7.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;
int function(int n)
{
    if (n == 1)
    {
        return 1;
    }
    if (n == 2)
    {
        return 2;
    }
    if (n == 3)
    {
        return 1;
    }
    if (n == 4)
    {
        return 2;
    }
    if (n == 5)
    {
        return 1;
    }
    int h[3] = { 1,3,5 };
    int Mincount = n;
    int count = 0;
    for (int i = 0; i < 3; i++)
    {
        count = function(n - h[i]) + 1;
        if(count < Mincount)
        {
            Mincount = count;
        }
    }
    return Mincount;
}

int main()
{
    int n = function(11);
    cout << n;
    system("pause");
    return 0;
}