线性规划算法实现二-----多状态线形规划

概述1 小明喜欢吃烤串，小明每次去烤串摊都会吃K支烤串。已知烤串摊有N种烤串，每种烤串有M支，问小明共有多少种不同的点餐组合。 2 #include "pch.h" 3 #include <iostream> 4 using namespace std; 5 6 unsigned long long test(int K, int N, int M) 7 { 8

 1 小明喜欢吃烤串，小明每次去烤串摊都会吃K支烤串。已知烤串摊有N种烤串，每种烤串有M支，问小明共有多少种不同的点餐组合。@H_419_9@  

 2 #include "@H_419_9@pch.h@H_419_9@"@H_419_9@ 3@H_419_9@ #include <iostream> 4@H_419_9@ using@H_419_9@ namespace@H_419_9@ std;@H_419_9@ 5@H_419_9@  6@H_419_9@ unsigned long@H_419_9@ long@H_419_9@  test(int@H_419_9@ K,int@H_419_9@ N,int@H_419_9@ M)@H_419_9@ 7@H_419_9@ {@H_419_9@ 8@H_419_9@     if@H_419_9@ (K <= 0@H_419_9@ || N <= 0@H_419_9@ || M <= 0@H_419_9@)return@H_419_9@ 0@H_419_9@;@H_419_9@ 9@H_419_9@     //@H_419_9@一样可计算出结果，但没必要算@H_419_9@10@H_419_9@     if@H_419_9@ (K > N * M)return@H_419_9@ 0@H_419_9@;@H_419_9@11@H_419_9@     if@H_419_9@ (K == N * M)return@H_419_9@ 1@H_419_9@;@H_419_9@12@H_419_9@     int@H_419_9@ L = K < M ? K : M;@H_419_9@13@H_419_9@     unsigned int@H_419_9@ ***p = new@H_419_9@  unsigned int@H_419_9@**[N];@H_419_9@14@H_419_9@     15@H_419_9@     for@H_419_9@ (int@H_419_9@ i = 0@H_419_9@; i < N; i++)@H_419_9@16@H_419_9@     {@H_419_9@17@H_419_9@         p[i] = new@H_419_9@ unsigned int@H_419_9@ *[L + 1@H_419_9@];@H_419_9@18@H_419_9@         for@H_419_9@ (int@H_419_9@ j = 0@H_419_9@; j <= L; j++)@H_419_9@19@H_419_9@         {@H_419_9@20@H_419_9@             //@H_419_9@全初始化为0@H_419_9@21@H_419_9@             p[i][j] = new@H_419_9@ unsigned int@H_419_9@[K + 1@H_419_9@]();@H_419_9@22@H_419_9@         }@H_419_9@23@H_419_9@     }
        //此处从0开始是因为列数0用于累计所有的未选择项，简单来说，就是统计跨层迭代，从而可以只观察上一层就可以计算出跨层的累计迭代数          @H_419_9@24@H_419_9@     for@H_419_9@ (int@H_419_9@ i = 0@H_419_9@; i <= L; i++)@H_419_9@25@H_419_9@     {@H_419_9@26@H_419_9@         p[0@H_419_9@][i][i] = 1@H_419_9@;@H_419_9@27@H_419_9@     }@H_419_9@28@H_419_9@     for@H_419_9@ (int@H_419_9@ i = 1@H_419_9@; i < N; i++)@H_419_9@29@H_419_9@     {@H_419_9@30@H_419_9@         //@H_419_9@吃j串状态@H_419_9@31@H_419_9@         for@H_419_9@ (int@H_419_9@ j = 0@H_419_9@; j <= L; j++)@H_419_9@32@H_419_9@         {@H_419_9@33@H_419_9@             //@H_419_9@吃完总计串数为k@H_419_9@34@H_419_9@             for@H_419_9@ (int@H_419_9@ k = 0@H_419_9@; k <= K; k++)@H_419_9@35@H_419_9@             {@H_419_9@36@H_419_9@ 37@H_419_9@                 for@H_419_9@ (int@H_419_9@ l = 0@H_419_9@; l <= L; L++)@H_419_9@38@H_419_9@                 {@H_419_9@39@H_419_9@                     //@H_419_9@此轮吃完j串总计k串的方法共有上一轮所有选择剩下k-j的方法数@H_419_9@40@H_419_9@                     if@H_419_9@ (k - j >= 0@H_419_9@)@H_419_9@41@H_419_9@                         p[i][j][k] += p[i - 1@H_419_9@][l][k - j];@H_419_9@42@H_419_9@                 }@H_419_9@43@H_419_9@             }@H_419_9@44@H_419_9@         }@H_419_9@45@H_419_9@     }@H_419_9@46@H_419_9@     unsigned long@H_419_9@ long@H_419_9@ sum = 0@H_419_9@;@H_419_9@47@H_419_9@     for@H_419_9@ (unsigned int@H_419_9@ i = 0@H_419_9@; i <= L; i++)@H_419_9@48@H_419_9@     {@H_419_9@49@H_419_9@         sum += p[N - 1@H_419_9@][i][K];@H_419_9@50@H_419_9@     }@H_419_9@51@H_419_9@     //@H_419_9@防止内存泄漏@H_419_9@52@H_419_9@     for@H_419_9@ (int@H_419_9@ i = 0@H_419_9@; i < N; i++)@H_419_9@53@H_419_9@     {@H_419_9@54@H_419_9@ 55@H_419_9@         for@H_419_9@ (int@H_419_9@ j = 0@H_419_9@; j <= L; j++)@H_419_9@56@H_419_9@         {@H_419_9@57@H_419_9@             //@H_419_9@全初始化为0@H_419_9@58@H_419_9@             delete@H_419_9@[]p[i][j];@H_419_9@59@H_419_9@         }@H_419_9@60@H_419_9@         delete@H_419_9@[]p[i];@H_419_9@61@H_419_9@     }@H_419_9@62@H_419_9@     delete@H_419_9@[]p;@H_419_9@63@H_419_9@     return@H_419_9@ sum;@H_419_9@64@H_419_9@ }@H_419_9@65@H_419_9@ 66@H_419_9@ int@H_419_9@ main()@H_419_9@67@H_419_9@ {@H_419_9@68@H_419_9@ 69@H_419_9@     int@H_419_9@ N,M,K;@H_419_9@70@H_419_9@     cout << "@H_419_9@请输入要吃的窜数@H_419_9@"@H_419_9@ << endl;@H_419_9@71@H_419_9@     cin >> K;@H_419_9@72@H_419_9@     cout << "@H_419_9@请输入种类数@H_419_9@"@H_419_9@ << endl;@H_419_9@73@H_419_9@     cin >> N;@H_419_9@74@H_419_9@     cout << "@H_419_9@请输入每种的数量@H_419_9@"@H_419_9@ << endl;@H_419_9@75@H_419_9@     cin >> M;@H_419_9@76@H_419_9@     cout << "@H_419_9@一共可以有 @H_419_9@"@H_419_9@ << test(K,N,M) << "@H_419_9@ 种吃法@H_419_9@"@H_419_9@ << endl;;@H_419_9@77@H_419_9@ }

 

若此题使用函数调用遍历，非常简单，但即使是使用优化剪枝一样可能导致栈溢出

直接遍历法，每次决策吃第i种j串，都得继续遍历余下所有的可能，直至到决策n为止（做 了算法剪枝也差不多）

                 

下面即为直接函数调用方法进行遍历

 1@H_419_9@ //@H_419_9@待优化，数值过大时，栈过深@H_419_9@ 2@H_419_9@ #include "@H_419_9@pch.h@H_419_9@"@H_419_9@ 3@H_419_9@ #include <iostream> 4@H_419_9@ #include<string@H_419_9@> 5@H_419_9@  6@H_419_9@ using@H_419_9@ namespace@H_419_9@ std;@H_419_9@ 7@H_419_9@ /*@H_419_9@ 8@H_419_9@  9@H_419_9@ 四、小明喜欢吃烤串，小明每次去烤串摊都会吃K支烤串。已知烤串摊有N种烤串，每种烤串有M支，问小明共有多少种不同的点餐组合@H_419_9@10@H_419_9@ //设相同种类同数量为1个点餐组合，即 A1 B19 无论A出现在哪均为一种,那么为了模拟不重复，选择了一种的数量后，后面就不能选择选择过的@H_419_9@11@H_419_9@ */@H_419_9@12@H_419_9@ unsigned long@H_419_9@ long@H_419_9@ f( int@H_419_9@ n,int@H_419_9@ left,int@H_419_9@ M)@H_419_9@13@H_419_9@ {@H_419_9@14@H_419_9@     15@H_419_9@     //@H_419_9@吃完@H_419_9@16@H_419_9@     if@H_419_9@ (left == 0@H_419_9@)return@H_419_9@ 1@H_419_9@;@H_419_9@17@H_419_9@     //@H_419_9@没有下一种了@H_419_9@18@H_419_9@     if@H_419_9@ (n > N)return@H_419_9@ 0@H_419_9@;@H_419_9@19@H_419_9@     unsigned long@H_419_9@ long@H_419_9@ sum = 0@H_419_9@;@H_419_9@20@H_419_9@ 21@H_419_9@     for@H_419_9@ (int@H_419_9@ i = 0@H_419_9@; i <=left&&i<=M; i++)@H_419_9@22@H_419_9@     {@H_419_9@23@H_419_9@         sum =sum+ f(n + 1@H_419_9@,left - i,M);@H_419_9@24@H_419_9@     }@H_419_9@25@H_419_9@     26@H_419_9@     return@H_419_9@ sum;@H_419_9@27@H_419_9@ }@H_419_9@28@H_419_9@ unsigned long@H_419_9@ long@H_419_9@ test(int@H_419_9@ K,int@H_419_9@ M)@H_419_9@29@H_419_9@ {@H_419_9@30@H_419_9@     unsigned long@H_419_9@ long@H_419_9@ result = 0@H_419_9@;@H_419_9@31@H_419_9@     //@H_419_9@非法数据@H_419_9@32@H_419_9@     if@H_419_9@ (K == 0@H_419_9@||N==0@H_419_9@||M==0@H_419_9@)return@H_419_9@ 0@H_419_9@;@H_419_9@33@H_419_9@     //@H_419_9@没有吃够的吃法@H_419_9@34@H_419_9@     if@H_419_9@ (K > N*M)return@H_419_9@ 0@H_419_9@;@H_419_9@35@H_419_9@     //@H_419_9@选择第N种烧烤@H_419_9@36@H_419_9@     for@H_419_9@ (int@H_419_9@ i = 0@H_419_9@; i <=M&&i <=K; i++)@H_419_9@37@H_419_9@     {@H_419_9@38@H_419_9@         result = result + f(2@H_419_9@,K-i,M);@H_419_9@39@H_419_9@     }@H_419_9@40@H_419_9@     return@H_419_9@ result;@H_419_9@41@H_419_9@ }@H_419_9@42@H_419_9@ 43@H_419_9@ int@H_419_9@ main()@H_419_9@44@H_419_9@ {@H_419_9@45@H_419_9@ 46@H_419_9@     int@H_419_9@ N,K;@H_419_9@47@H_419_9@     cout << "@H_419_9@请输入要吃的窜数@H_419_9@"@H_419_9@ << endl;@H_419_9@48@H_419_9@     cin >> K;@H_419_9@49@H_419_9@     cout << "@H_419_9@请输入种类数@H_419_9@"@H_419_9@ << endl;@H_419_9@50@H_419_9@     cin >> N;@H_419_9@51@H_419_9@     cout << "@H_419_9@请输入每种的数量@H_419_9@"@H_419_9@ << endl;@H_419_9@52@H_419_9@     cin >> M;@H_419_9@53@H_419_9@     cout << "@H_419_9@一共可以有 @H_419_9@"@H_419_9@ << test(K,M) << "@H_419_9@ 种吃法@H_419_9@"@H_419_9@ << endl;;@H_419_9@54@H_419_9@ }

 

一、@H_419_9@@H_419_9@ 小明喜欢吃烤串，小明每次去烤串摊都会吃@H_419_9@K@H_419_9@支烤串。已知烤串摊有@H_419_9@N@H_419_9@种烤串，每种烤串有@H_419_9@M@H_419_9@支，问小明共有多少种不同的点餐组合。@H_419_9@

 @H_419_9@   @H_419_9@@H_419_9@#include@H_419_9@"pch.h"@H_419_9@

#include@H_419_9@<iostream>@H_419_9@

using@H_419_9@namespace@H_419_9@ std;@H_419_9@

 @H_419_9@

unsigned@H_419_9@long@H_419_9@long@H_419_9@  @H_419_9@test(@H_419_9@int@H_419_9@K@H_419_9@,@H_419_9@int@H_419_9@N@H_419_9@,@H_419_9@int@H_419_9@M@H_419_9@)@H_419_9@

{@H_419_9@

    @H_419_9@@H_419_9@if@H_419_9@ (@H_419_9@K@H_419_9@ <= 0 || @H_419_9@N@H_419_9@ <= 0 || @H_419_9@M@H_419_9@ <= 0)@H_419_9@return@H_419_9@ 0;@H_419_9@

    @H_419_9@@H_419_9@//@H_419_9@一样可计算出结果，但没必要算@H_419_9@

    @H_419_9@@H_419_9@if@H_419_9@ (@H_419_9@K@H_419_9@ > @H_419_9@N@H_419_9@ * @H_419_9@M@H_419_9@)@H_419_9@return@H_419_9@ 0;@H_419_9@

    @H_419_9@@H_419_9@if@H_419_9@ (@H_419_9@K@H_419_9@ == @H_419_9@N@H_419_9@ * @H_419_9@M@H_419_9@)@H_419_9@return@H_419_9@ 1;@H_419_9@

    @H_419_9@@H_419_9@int@H_419_9@ L = @H_419_9@K@H_419_9@ < @H_419_9@M@H_419_9@ ? @H_419_9@K@H_419_9@ : @H_419_9@M@H_419_9@;@H_419_9@

    @H_419_9@@H_419_9@unsigned@H_419_9@int@H_419_9@ ***p = @H_419_9@new@H_419_9@  @H_419_9@@H_419_9@unsigned@H_419_9@int@H_419_9@**[@H_419_9@N@H_419_9@];@H_419_9@

    @H_419_9@@H_419_9@

    @H_419_9@@H_419_9@for@H_419_9@ (@H_419_9@int@H_419_9@ i = 0; i < @H_419_9@N@H_419_9@; i++)@H_419_9@

    @H_419_9@{@H_419_9@

        @H_419_9@p[i] = @H_419_9@new@H_419_9@unsigned@H_419_9@int@H_419_9@ *[L + 1];@H_419_9@

        @H_419_9@@H_419_9@for@H_419_9@ (@H_419_9@int@H_419_9@ j = 0; j <= L; j++)@H_419_9@

        @H_419_9@{@H_419_9@

            @H_419_9@@H_419_9@//@H_419_9@全初始化为0@H_419_9@@H_419_9@

            @H_419_9@p[i][j] = @H_419_9@new@H_419_9@unsigned@H_419_9@int@H_419_9@[@H_419_9@K@H_419_9@ + 1]();@H_419_9@

        @H_419_9@}@H_419_9@

    @H_419_9@}@H_419_9@

    @H_419_9@@H_419_9@for@H_419_9@ (@H_419_9@int@H_419_9@ i = 0; i <= L; i++)@H_419_9@

    @H_419_9@{@H_419_9@

        @H_419_9@p[0][i][i] = 1;@H_419_9@

    @H_419_9@}@H_419_9@

    @H_419_9@@H_419_9@for@H_419_9@ (@H_419_9@int@H_419_9@ i = 1; i < @H_419_9@N@H_419_9@; i++)@H_419_9@

    @H_419_9@{@H_419_9@

        @H_419_9@@H_419_9@//@H_419_9@吃j@H_419_9@串状态@H_419_9@

        @H_419_9@@H_419_9@for@H_419_9@ (@H_419_9@int@H_419_9@ j = 0; j <= L; j++)@H_419_9@

        @H_419_9@{@H_419_9@

            @H_419_9@@H_419_9@//@H_419_9@吃完总计串数为k@H_419_9@@H_419_9@

            @H_419_9@@H_419_9@for@H_419_9@ (@H_419_9@int@H_419_9@ k = 0; k <= @H_419_9@K@H_419_9@; k++)@H_419_9@

            @H_419_9@{@H_419_9@

 @H_419_9@

                @H_419_9@@H_419_9@for@H_419_9@ (@H_419_9@int@H_419_9@ l = 0; l <= L; L++)@H_419_9@

                @H_419_9@{@H_419_9@

                    @H_419_9@@H_419_9@//@H_419_9@此轮吃完j@H_419_9@串总计k@H_419_9@串的方法共有上一轮所有选择剩下k-j@H_419_9@的方法数@H_419_9@

                    @H_419_9@@H_419_9@if@H_419_9@ (k - j >= 0)@H_419_9@

                        @H_419_9@p[i][j][k] += p[i - 1][l][k - j];@H_419_9@

                @H_419_9@}@H_419_9@

            @H_419_9@}@H_419_9@

        @H_419_9@}@H_419_9@

    @H_419_9@}@H_419_9@

    @H_419_9@@H_419_9@unsigned@H_419_9@long@H_419_9@long@H_419_9@ sum = 0;@H_419_9@

    @H_419_9@@H_419_9@for@H_419_9@ (@H_419_9@unsigned@H_419_9@int@H_419_9@ i = 0; i <= L; i++)@H_419_9@

    @H_419_9@{@H_419_9@

        @H_419_9@sum += p[@H_419_9@N@H_419_9@ - 1][i][@H_419_9@K@H_419_9@];@H_419_9@

    @H_419_9@}@H_419_9@

    @H_419_9@@H_419_9@//@H_419_9@防止内存泄漏@H_419_9@

    @H_419_9@@H_419_9@for@H_419_9@ (@H_419_9@int@H_419_9@ i = 0; i < @H_419_9@N@H_419_9@; i++)@H_419_9@

    @H_419_9@{@H_419_9@

 @H_419_9@

        @H_419_9@@H_419_9@for@H_419_9@ (@H_419_9@int@H_419_9@ j = 0; j <= L; j++)@H_419_9@

        @H_419_9@{@H_419_9@

            @H_419_9@@H_419_9@//@H_419_9@全初始化为0@H_419_9@@H_419_9@

            @H_419_9@@H_419_9@delete[]@H_419_9@p[i][j];@H_419_9@

        @H_419_9@}@H_419_9@

        @H_419_9@@H_419_9@delete[]@H_419_9@p[i];@H_419_9@

    @H_419_9@}@H_419_9@

    @H_419_9@@H_419_9@delete[]@H_419_9@p;@H_419_9@

    @H_419_9@@H_419_9@return@H_419_9@ sum;@H_419_9@

}@H_419_9@

 @H_419_9@

int@H_419_9@ main()@H_419_9@

{@H_419_9@

 @H_419_9@

    @H_419_9@@H_419_9@int@H_419_9@ N,K;@H_419_9@

    @H_419_9@cout @H_419_9@<<@H_419_9@"@H_419_9@请输入要吃的窜数"@H_419_9@@H_419_9@<<@H_419_9@ endl;@H_419_9@

    @H_419_9@cin @H_419_9@>>@H_419_9@ K;@H_419_9@

    @H_419_9@cout @H_419_9@<<@H_419_9@"@H_419_9@请输入种类数"@H_419_9@@H_419_9@<<@H_419_9@ endl;@H_419_9@

    @H_419_9@cin @H_419_9@>>@H_419_9@ N;@H_419_9@

    @H_419_9@cout @H_419_9@<<@H_419_9@"@H_419_9@请输入每种的数量"@H_419_9@@H_419_9@<<@H_419_9@ endl;@H_419_9@

    @H_419_9@cin @H_419_9@>>@H_419_9@ M;@H_419_9@

    @H_419_9@cout @H_419_9@<<@H_419_9@"@H_419_9@一共可以有 "@H_419_9@@H_419_9@<<@H_419_9@ test(K,M) @H_419_9@<<@H_419_9@" @H_419_9@种吃法"@H_419_9@@H_419_9@<<@H_419_9@ endl;;@H_419_9@

}@H_419_9@

总结

以上是内存溢出为你收集整理的线性规划算法实现二-----多状态线形规划全部内容，希望文章能够帮你解决线性规划算法实现二-----多状态线形规划所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。