转载于:https://my.oschina.net/liyangke/blog/2985952

资源分配(链接)

资源分配问题就是将一定数量的一种或若干种资源（原材料、资金、设备等）合理分配给若干使用者，使得资源分配后总结果最优。一种资源的分配问题称为一维资源分配问题，两种资源的分配问题称为二维资源分配问题。

假设有一种资源，数量为a，将其分配给n个使用者，分配给第 i 个使用者数量 xi 时，相应的收益为gi（xi） . 问如何分配使得总收入最大？这就是一维资源分配问题，该问题的数学模型为：
                                             

这是一个静态规划问题，应用动态规划方法求解时，人为赋予时间概念，将其看作是一个多阶段决策问题。

1.机器分配问题

总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

输入格式：

第一行有两个数，第一个数是分公司数N，第二个数是设备台数M。

接下来是一个N*M的矩阵，表明了第  i 个公司分配  j 台机器的盈利。

输出格式：

第1行为最大盈利值

第2到第n为第i分公司分x台

输入样例#1：

3 3
30 40 50
20 30 50
20 25 30

输出样例#1：

70
1 1
2 1
3 1

要求资源分配的最大值，我们可以用二维数组 f[i][j] 来表示前 i 个公司得到 j 台机器后所得到的最大盈利值。

那么我们就可以得到 前 1~i-1 个公司取 k 台机器，而 剩下的 j-k 台机器给 第 i 个公司

方程是：

f[i][j]=max(f[i][j],f[i-1][k]+a[i][j-k]);

f[i-1][k] 表示前i-1个公司取k台机器的最大值，a[i][j-k] 表示第i个公司取剩余的k台机器的利益，那么 f[i-1][k]+a[i][j-k] 表示的就是第 i 个公司不取 k 台机器所得到的最大值

        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k <= j; k++) {
                    //此时共有 j 台机器，前 i 个公司，分配 j 台机器的最大价值
                    //全部分给前i个公司，或者前 i-1 个公司分k台，第i个公司分j-k台
                    //循环k 取最大值
                    f[i][j] = Math.max(f[i][j], f[i - 1][k] + a[i][j - k]);
                }
            }
        }

 此时共有 j 台机器，前 i 个公司，分配 j 台机器的最大价值 .全部分给前i个公司，或者前 i-1 个公司分k台，第i个公司分j-k台 循环k 取最大值

代码如下：

import java.util.Scanner;

public class 机器分配 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//分公司数
        int m = sc.nextInt();//设备数
        int[][] a = new int[n + 1][m + 1];//第 i 个公司分配 j 台机器的盈利。
        //输入
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = sc.nextInt();
            }
        }

        // f[i][j]表示前 i 个公司，分配 j 台机器的最大价值
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k <= j; k++) {
                    //此时共有 j 台机器，前 i 个公司，分配 j 台机器的最大价值
                    //全部分给前i个公司，或者前 i-1 个公司分k台，第i个公司分j-k台
                    //循环k 取最大值
                    f[i][j] = Math.max(f[i][j], f[i - 1][k] + a[i][j - k]);
                }
            }
        }
        System.out.println(f[n][m]);
    }
}

2.修理马棚

题目描述

每天，小明和他的马外出，然后他们一边跑一边玩耍。当他们结束的时候，必须带所有的马返回马棚，小明有K个马棚。他把他的马排成一排然后跟随它走向马棚，因为他们非常疲劳，小明不想让他的马做过多的移动。因此他想了一个办法：将马按照顺序放在马棚中，后面的马放的马棚的序号不会大于前面的马放的马棚的序号。而且，他不想他的K个马棚中任何一个空置，也不想任何一匹马在外面。已知共有黑、白两种马，而且它们相处得并不十分融洽。如果有 i 个白马和 j 个黑马在一个马棚中，那么这个马棚的不愉快系数将是 i*j 。所有 k 个马棚不愉快系数的和就是系数总和。现在请你确定一种方法把 n 匹马放入 k 个马棚，使得系数总和最小 。

输入格式

在第一行有两个数字：n（1≤n≤500）和 k（1≤k≤n）。在接下来的n行是n个数。在这些行中的第i行代表队列中的第i匹马的颜色：1意味着马是黑色的，0意味着马是白色的。

输出格式

只输出一个单一的数字，代表系数总和达到的最小值。

样例输入

6 3

1

1

0

1

0

1

样例输出

2

数据范围

1≤n≤500，1≤k≤n

设 f[i][j] 为前 i 个马棚放下j匹马能得到的最小不愉快系数,

f[i][j]=min(f[i][j],f[i-1][k1]+t[k1+1][j]).，同样枚举k1 ,前i-1个马棚放k1头的最少冲突值加上第i个牛棚放剩下的马的冲突值

代码如下：

import java.util.Scanner;

public class 修理马棚 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//n匹马
        int k = sc.nextInt();//k个马棚
        int[] a = new int[n + 1];//保存是黑马还是白马

		//输入
        for (int i = 1; i <= n; i++)
            a[i] = sc.nextInt();
		
		//如果有 i 个白马和 j 个黑马在一个马棚中，那么这个马棚的不愉快系数将是 i*j 
		
        int[] one = new int[n];//前缀和one[i]和two[i]来记录到 i 时白马和黑马的数量，用01区更方便
        int[] two = new int[n];
        int[][] t = new int[n + 1][n + 1];// t[i][j]表示 i 到 j 的冲突值
        int[][] f = new int[n + 1][n + 1];//f[i][j] 为前 i 个马棚放下 j 匹马能得到的最小不愉快系数,
        for (int i = 1; i <= n; i++) {
			//前 i 个有多少个白马
            if (a[i] == 1) {
                one[i] = one[i - 1] + 1;
            } else {
                one[i] = one[i - 1];
            }
			//前 i 个有多少个黑马
            if (a[i] == 0) {
                two[i] = two[i - 1] + 1;
            } else {
                two[i] = two[i - 1];
            }
        }

        //预处理
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
				//t[i][j]表示 前 i到j 中白马与黑马的不愉快系数
                t[i][j] = Math.abs(one[j] - one[i - 1]) * Math.abs(two[j] - two[i - 1]);//预处理
            }
        }
		//一个马棚放下 i 匹马的不愉快系数就是 t[1][i]
        for (int i = 1; i <= n; i++)
            f[1][i] = t[1][i];
		//i 个马棚放一匹马的不愉快系数是0
        for (int i = 1; i <= n; i++)
            f[i][1] = 0; //初始化
		
        for (int i = 2; i <= k; i++){
            for (int j = 1; j <= n; j++) {
                for (int k1 = 0; k1 < j; k1++)
					//前 i-1个马棚k1个马，第i个放 j-k1匹马
                    f[i][j] = Math.min(f[i][j], f[i - 1][k1] + t[k1 + 1][j]);
            }//动态规划
		}
        System.out.println(f[n][k]);

    }
}

快餐问题：

题目描述 

Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。价格便宜。为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡、薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡、薯条和饮料的单位生产时间又不同，这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编写程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。

输入描述 

第一行为三个不超过100的正整数A、B、C，中间以一个空格分开；

第二行为三个不超过100的正整数p1、p2、p3分别为汉堡、薯条和饮料的单位生产耗时。中间以一个空格分开。

第三行为一个整数N(0≤N≤10)代表流水线；

第四行为M个不超过10000的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。

输出描述 

输出文件仅一行，即每天套餐的最大产量。

样例输入 

1 2 1

1 2 1

5

16 16 8 9 14

样例输出

10

分享一下我老师大神的人工智能教程！零基础，通俗易懂！http://blog.csdn.net/jiangjunshow

也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！

//列大小固定的二维数组可以申请一维数据并将指针强转成二维数组#include <stdio.h>int main(){ printf("  列大小固定的二维数组可以申请一维数据并将指针强转成二维数组\n");   printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");   //列值固定 const int MAXCOL = 3; int nRow; printf("请输入二维数组的行数(列值固定为%d): ", MAXCOL); scanf("%d", &nRow); //申请一维数据并将其转成二维数组指针 int *pp_arr = new int[nRow * MAXCOL]; int (*p)[MAXCOL] = (int(*)[MAXCOL])pp_arr; //为二维数组赋值 int i, j; for (i = 0; i < nRow; i++)  for (j = 0; j < MAXCOL; j++)   p[i][j] = i + j;  //输出二维数组 for (i = 0; i < nRow; i++) {  for (j = 0; j < MAXCOL; j++)   printf("%5d", p[i][j]);  putchar('\n'); } //释放资源 delete[] pp_arr; return 0;}

//C语言中动态的申请二维数组 malloc free#include <stdio.h>#include <stdlib.h>#include <string.h>//动态申请二维数组template <typename T>T** malloc_Array2D(int row, int col){ int size = sizeof(T); int point_size = sizeof(T*); //先申请内存，其中point_size * row表示存放row个行指针 T **arr = (T **) malloc(point_size * row + size * row * col); if (arr != NULL) {   memset(arr, 0, point_size * row + size * row * col);  T *head = (T*)((int)arr + point_size * row);  while (row--)   arr[row] = (T*)((int)head + row * col * size); } return (T**)arr;}//释放二维数组void free_Aarray2D(void **arr){ if (arr != NULL)  free(arr);}int main(){ printf("  C语言中动态的申请二维数组 malloc free\n");   printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n"); printf("请输入行列(以空格分开): "); int nRow, nCol; scanf("%d %d", &nRow, &nCol); //动态申请连续的二维数组 int **p = malloc_Array2D<int>(nRow, nCol); //为二维数组赋值  int i, j;  for (i = 0; i < nRow; i++)  for (j = 0; j < nCol; j++)   p[i][j] = i + j; //输出二维数组  for (i = 0; i < nRow; i++) {  for (j = 0; j < nCol; j++)   printf("%4d ", p[i][j]);  putchar('\n'); } free_Aarray2D((void**)p); return 0;}

//C++语言中动态的申请二维数组 new delete#include <new>#include <cstdio>#include <cstdlib>#include <string>using namespace std;//动态申请二维数组template <typename T>T** new_Array2D(int row, int col){ int size = sizeof(T); int point_size = sizeof(T*); //先申请内存，其中sizeof(T*) * row表示存放row个行指针 T **arr = (T **) malloc(point_size * row + size * row * col); if (arr != NULL) {   T *head = (T*)((int)arr + point_size * row);  for (int i = 0; i < row; ++i)  {   arr[i] =  (T*)((int)head + i * col * size);   for (int j = 0; j < col; ++j)    new (&arr[i][j]) T;  } } return (T**)arr;}//释放二维数组template <typename T>void delete_Array2D(T **arr, int row, int col){ for (int i = 0; i < row; ++i)  for (int j = 0; j < col; ++j)   arr[i][j].~T(); if (arr != NULL)  free((void**)arr);}int main(){ printf("  C++语言中动态的申请二维数组 new delete\n");   printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n"); printf("请输入行列(以空格分开): "); int nRow, nCol; scanf("%d %d", &nRow, &nCol); //动态申请连续的二维数组 string **p = new_Array2D<string>(nRow, nCol); //为二维数组赋值 int i, j; for (i = 0; i < nRow; i++)  for (j = 0; j < nCol; j++)  {   char szTemp[30];   sprintf(szTemp, "(第%d行,第%d列)", i, j);   p[i][j] = szTemp;  } //输出二维数组  for (i = 0; i < nRow; i++) {  for (j = 0; j < nCol; j++)   printf("%s ", p[i][j].c_str());  putchar('\n'); } delete_Array2D<string>(p, nRow, nCol); return 0;}

给我老师的人工智能教程打call！http://blog.csdn.net/jiangjunshow