c语言整数划分

[C语言数组排序]#include<stdio.h> void main() { int a[10] = { 10,2,3,4,5,6,9,8,7,1 }; int i,j,t; for(j=0;j<10;j++) for(i=0;i<10-1-j;i++) if(a[i]>a[i+1]) /* 由小到大，由大到小时改...+阅读

经典题：

#include

using namespace std;

#define size 4501

int n, m, dp[size][size];

int main()

{

scanf(＂%d%d＂, &n ,&m);

for(int i = 1; i <= m; i++) dp[1][i] = 1;

for(int i = 2; i <= n; i++)

{

for(int j = 1; j <= m; j++)

{

dp[i][j] = dp[i - 1][j];

if (i == j) dp[i][j]++;

if (j > i) dp[i][j] += dp[i][j - i];

if (dp[i][j] >= 1000000007) dp[i][j] -= 1000000007;

}

printf(＂%d\n＂, dp[n][m]);

return 0;

}

整数规划的分类

整数规划英文（integer programming）

定义：

在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求某些变量的解必须是整数。例如，当变量代表的是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是01规划，它的变数仅限于0或1。不同于线性规划问题，整数和01规划问题至今尚未找到一般的多项式解法。

组合最优化

组合最优化通常都可表述为整数规划问题。两者都是在有限个可供选择的方案中，寻找满足一定约束的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、旅行推销员问题，车辆路径问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。

整数规划

整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。现今比较成功又流行的方法是分支定界法和割平面法，它们都是在上述框架下形成的。

0—1规划

0—1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0—1规划等价，用0—1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0—1规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。

整数的划分问题要求将所有可能性输出用Java或c都可以

import java.util.HashMap; import java.util.Map; public class Test { private static void getString(String t, int h, int o, Map map) { if (h > o) { getString(t, o, o, map); } else { if (h < o) { getString(h + ＂+＂ + t, h, o - h, map); for (int i = h - 1; i >= 2; i--) { getString(h + ＂+＂ + t, i, o - h, map); } } else { String out = h + ＂+＂ + t; out = out.substring(0, out.length() - 1); map.put(out, out); for (int i = h - 1; i >= 2; i--) { getString(t, i, o, map); } } String out = t + ＂＂; for (int x = 0; x < o; x++) out = 1 + ＂+＂ + out; out = out.substring(0, out.length() - 1); map.put(out, out); } } public static void outAll(int n) { Map map = new HashMap(); getString(＂＂, n, n, map); for (String key : map.keySet()) { System.out.println(key); } } public static void main(String[] args) { outAll(6); } }