∩)o...)我就是这么wa了一次,线性动态规划是指目标函数为特定变量的线性函数

  • 栏目:基础 时间:2020-01-28 14:51
<返回列表

动态规划:

To The Max

线性动态规划

  不要想当然的以为最小值就是0,(o(∩_∩)o...)我就是这么wa了一次。

Problem Description
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.

一、定义

 

As an example, the maximal sub-rectangle of the array:

    线性动态规划是指目标函数为特定变量的线性函数,约束是这些变量的线性不等式或等式,目的是求目标函数的最大值或最小值。

代码:

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

二、典型例题

 

is in the lower left corner:

    1、最长上升序列问题

 

9 2
-4 1
-1 8

    问题描述:设有序列B为B1,B2,B3……Bn,若存在下标i1<i2<i3<……in,且Bi1<Bi2<Bi3<……Bin,则序列B中有长度为n的上升序列Bi1,Bi2,Bi3,……Bin。求给定一序列中的最长上升序列长度及该序列。

#include <iostream>
using namespace std;
long sum[101]={0};
long tempsum[101]={0};
long bunch[101][101]={0};
long max(int i, int j)//求最大值
{

and has a sum of 15.  

分析:

 long temp=-2147483648;
 for(int s=i;s<=j;s++)
 {
  if(sum[s]>temp)
   temp=sum[s];
 }
 return temp;
}
void build_summax(int i,int j)//动态规划核心部分
{
 tempsum[j]=max(i-1,j-1)+bunch[i][j];
}
void truesum(int V)//得SUM
{
 for(int j=0;j<V;j++)
  sum[j]=tempsum[j];
}
main()
{
 int F,V;
 cin >>F>>V;
 for(int i=0;i<F;i++)
  for(int j=0;j<V;j++)
   cin>>bunch[i][j];

Input
The input consists of an N x N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N 2 integers separated by whitespace (spaces and newlines). These are the N 2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].  

    ①设f(i)是前i个数中以Bi结尾的最长上升序列的长度,

  for(i=0;i<V;i++)//初始化第一行
  {
   sum[i]=bunch[0][i];
   tempsum[i]=bunch[0][i];
  }

Output
Output the sum of the maximal sub-rectangle.  

则f(i)=max(f(j)+1),  (1<=j<i<=n,Bj<Bi),边界为f(1)=1;

  for(i=1;i<F;i++)//注意约束
  {
   for(int j=i;j<V;j++)
   build_summax(i,j);
  truesum(V);
  }
  cout<<max(F-1,V-1)<<endl;
  return 0;
}

Sample Input
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2  

    ②设t(i) 是前i个数中所有最长上升序列的个数,初始t(i)=1,如果f(i)=n时,将t(i)累加,(   1<=j<i<=n , Bi<Bj , f(i)=f(j)+1 )

 

Sample Output
15
 
题目我起先用暴力法来解答,不过,通不过,超时,后来参考了一下别人的思想吧!没想到这道题还可以用动归的方法解答,很吃惊啊!
代码如下:
[cpp] 
//这个程序可以求出m*n的矩阵某一块的最大值 
//这种搜索算法没有错误!但是超时,因此还要进一步优化算法! 
//这道题的题意说的比较模糊,题目里没有说要多个测试数据,弄得我只处理了一次,导致老是错误,又找不到问题所在! 
/*
#include<iostream>
#include<cstdio>
using namespace std;
const int MAX=10010;
int arr[MAX];
 
int main()
{
    int s,max=-200;
    int we=0;
    int m,n;
    while(scanf("%d",&arr[0])!=EOF)
    {
    //cin>>arr[0];//输入方阵的维数
    m=n=arr[0];
    for(int i=1;i<=arr[0]*arr[0];i++)
        cin>>arr[i];
 
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)//这里是表示块数的大小,i*j
            for(int p=1;m-p>=i-1 ;p++)
                for(int q=1;n-q>=j-1 ;q++)//搜索路线,自上而下,自左向右
                {
                    int cur=p+m*(q-1);
                    int count=0;
                    int temp=cur; 
                    int temp1=1;
                    s=0;
                    //cout<<"第"<<we<<"次搜索: "<<endl;
                    //cout<<"起点是 行数"<<p<<","<<"列数"<<q<<endl;
                    //cout<<"p="<<p<<",n="<<n<<endl;
                    for(int k=1;k<=i*j;k++)
                    {
                        //cout<<arr[temp]<<"  ";
                        s=s+arr[temp];
                        count++;
                        temp++;
                        if(count>=i)
                        {
                            temp=cur+temp1*m;
                            temp1++;
                            count=0;
                        }
                    }
                    //cout<<endl;
                    //we++;
                    if(s>max)
                    max=s;
                }
     cout<<max<<endl;
     //system("pause");
     }
    return 0;
}
*/ 
 
#include<iostream> 
#include<cstdio> 
using namespace std; 
 
int arr[101][101]; 
int sum[101],dp[101]; 
 
int main() 

     
    int i,j,k,p,n; 
    while(scanf("%d",&n)!=EOF) 
    {   
        int max=-200; 
        memset(sum,0,sizeof(sum)); 
        memset(dp,0,sizeof(dp)); 
        for(i=0;i<n;i++) 
            for(j=0;j<n;j++) 
            cin>>arr[i][j]; 
        //很难想到,这居然是一道动态规划题 
        //1、最大子字段和 
    /*
    题目可以转化为两个子问题:
    1,给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a+a+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0,依此定义,所求的最优值为Max{0,a+a+…+a[j]},1<=i<=j<=n
    我们把b[j]理解为从前面某项开始包含a[j](a[j]为最后一个元素)的连续的段的和最大值,易知,开始的a[i]必定为正数!
记b[j]=max(a+..+a[j-1]+a[j]),其中1<=i<=j,并且1<=j<=n,需要明确的一点是b[j]的值必须包含a[j]。则所求的最大子段和为max{b[j]},1<=j<=n。
    由b[j]的定义可易知,当b[j-1]>0时(即前面的段加上a[j]这一段值会更大,自然把a[j]这一段接上)b[j]=b[j-1]+a[j],否则(由于前面的段为负值,加上a[j],会使值变小,这样的话,我们将前面的段去掉,a[j]即是最大值)b[j]=a[j]。故b[j]的动态规划递归式为 b[j]=max(b[j-1]+a[j],a[j]),1<=j<=n。
    2、最大子矩阵和
 
    矩阵是二维的,将其压缩成一维就可以用上面的方法求出最大子矩阵和了
    即将一层层的数相加,压缩成一维的即可,我们遍历所有的压缩可能,就可以通过上面的方法,求出最大值!
    */  
        for(i=0;i<n;i++) 
        { 
            memset(sum,0,sizeof(sum)); 
            for(k=i;k<n;k++) 
            { 
                for(j=0;j<n;j++) 
                sum[j]=arr[k][j]+sum[j]; 
                    dp[0]=sum[0]; 
                    for(p=1;p<n;p++) 
                    { 
                        if (dp[p-1]>0) dp[p]=dp[p-1]+sum[p]; 
                        else dp[p]=sum[p]; 
                        if (dp[p]>max) max=dp[p]; 
                        /*
                        if(dp[p-1]+sum[p]>sum[p])
                            dp[p]=dp[p-1]+sum[p];
                        else
                            dp[p]=dp[p-1];
                        if(dp[p]>max) max=dp[p];
                        */ 
                    } 
                     
            } 
        } 
        cout<<max<<endl; 
        //system("pause"); 
    } 
    return 0; 

例如

Bi

1

5

3

4

6

5

8

10

9

8

7

f(i)

1

2

2

3

4

4

5

6

6

5

5

T(i)

1

1

2

1

1

2

2

2

4

4

4

 

代码:

/*

*求最长上升子序列的元素的个数

*/

public class Long_list {

   public static void main(String[] args) {

      int s[]={1,5,3,4,6,5,8,10,9};

      int [] f=new int[s.length];

      int [] t=new int[s.length];

      f[0]=1;

      int maxLen=0;

      for (int i = 0; i < s.length; i++) {

         for (int j = 0; j < i; j++) {

            if(s[i]>s[j]&&f[j]+1>f[i])

                f[i]=f[j]+1;

         }

         if(maxLen<f[i])

            maxLen=f[i];

      }

      System.out.println(f[f.length-1]);

      Long_list l=new Long_list();

      //System.out.println(l.LIS_BSearch(s, t, s.length-1));

   }

}

 

//求最长上升子序列

 

public class LIS {

 

/*

 

 * 求一数列的最长上升子序列(元素都为非零元素)

 

 */

 

   public static void main(String[] args) {

 

      int []s ={1,2,9,4,6,7,4};

 

      //f数组来存储以其下标i(即s[i])结尾的最长上升序列元素的个数

 

      int []f = new int[s.length];

 

      //son数组来存储每个以s[i]结尾的最长上升子序列

 

      int [][]son = new int [s.length][s.length];

 

      f[0] = 1;

 

      int sum = 1;

 

      son[0][0] = s[0];

 

      for(int i=1;i<s.length;i++){

 

         for(int j=0;j<i;j++){

 

            if(s[i]>s[j]&&f[j]+1>f[i]){

 

                son[i][j] = s[j];

 

                f[i]=f[j]+1;

 

            }

 

         }

 

         son[i][i] = s[i];

 

         if(f[i]>sum) sum=f[i];

 

      }

 

      System.out.println("最长上升子序列的长度是 "+sum);

 

      int index = 0;

 

      int max = 0;

 

      for (int i = 0; i < son.length; i++) {

 

         int temp =0;

 

         for (int j = 0; j < son[0].length; j++) {

 

            if(son[i][j]!= 0) temp++;

 

         }

 

         if(temp>max){

 

            max = temp;

 

            index = i;

 

         }

 

      }

 

      System.out.print("最长上升子序列是:");

 

      for (int i = 0; i < s.length; i++) {

 

         if(son[index][i]!= 0)

 

         System.out.print(son[index][i]+" ");

 

      }

 

   }

 

}

 

    2、合唱队形

    问题描述:N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。   合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,  则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。

分析:

首先用枚举法求出以每个人作为中间最高的同学是需要出列的同学,再在这些数据中求出最小值,即为答案。

如何求出出列的同学呢?即总人数 –留在队伍中的同学数,求留在队伍中的同学的即转换为了从左右两头求最长上升子序列问题。

代码:

public class Formation {//合唱队形问题

   public static void main(String[] args) {

      int []s={1,2,3,5,2,4,1};

      int []lenL=new int[s.length];

      int []lenR=new int[s.length];

      lenR[0]=1;

      lenL[0]=1;

      for (int i = 0; i < lenL.length; i++) {

         for (int j = 0; j < i; j++) {

            if(s[i]>s[j]&&lenL[i]<lenL[j]+1)

                lenL[i]=lenL[j]+1;

         }

      }

      for (int i = lenR.length-1; i >= 0; i--) {

         for (int j = lenR.length-1; j > i; j--) {

            if(s[i]>s[j]&&lenR[i]<lenR[j]+1)

                lenR[i]=lenR[j]+1;

         }

      }

      int len=0,x=0;

      for (int i = 0; i < lenR.length; i++) {

         if(len<lenR[i]+lenL[i]){

            len=lenR[i]+lenL[i];

            x=i;

         }

      }

      System.out.println("需要出列"+(s.length-len)+"人");

      System.out.println("队伍剩余人数是"+len+"人");

      System.out.println("中间的同学的高度是"+s[x]);

   }

}

3、数字串加“+”的最值问题

    问题描述:设一个由0到9是个数字组成的字符串,向该   字符串中加n个“+”,得到一个加法式,并计算得到结果。问如何添加这n个“+”使得最后的运算结果最小,输出该最小值。

分析:首先列出规划方程

F(i,j)=min[F(i-1,k)+Number(k,j)] (i<=k<j)

F(i,j)表示对于该字符串的前j个数字中添加i个加号后的最小值。

Number(i,j)表示对该字符串的第i个位置到第j个位置截取后对应的整数的值。

代码:

public class String_add_plus {

   //fun(str,i,j)表示对于str的前j个数字中添加i个加号后的最小值

   private static int fun(String str,int i,int j) {

      if(i==0){

         return Integer.parseInt(str.substring(0,j));

      }

      int min=Integer.parseInt(str);

      for(int k=i;k<j;k++){

         int temp=fun(str,i-1,k)+Integer.parseInt(str.substring(k,j));

         if(min>temp)

            min=temp;

      }

      return min;

   }

   //测试

   public static void main(String[] args) {

      String str="1234";

      int min=fun(str,2,str.length());

      System.out.println(min);

   } 

}

4、子集和问题(硬币问题)

    问题描述:设S={x1,x2,x3……xn}是一个正整数的集合,C是一个正整数,子集和问题就是判断是否存在S的一个子集S1,使得S1中元素的和为C。

    经典问题:给定11种面值分别为100元, 50元, 20元, 10元, and 5元 and 2元, 1元, 50分, 20分, 10分 and 5分的钱,现在给定一个钱数,求出可以组成的种类数。

    问题分析:

    设c(i,j)是a1,a2……ai中包含ai且数和为j的方案数,显然目标是求c(n,T)。将前i个正整数设为阶段(1<=i<=n),将k1*a1+k2*a2+…..+ki*ai的可能数和j(ai<=j<=T)设为状态,显然状态转移方程为c(i,j)=1(i=0)或者c(i,j)=c(k,j-ai){k=1到k=i-1}的和。

 

5、最长公共子序列问题(Longest Common Subsequence,LCS)

问题描述:

首先明确最长公共子串(Longest Common Substirng)和最长公共子序列(Longest Common Subsequence,LCS)的区别。子串是串的一个连续的部分;子序列则是从不改变序列的顺序,而从序列中去掉任意的元素而获得新的序列。也就是说,子串中字符的位置必须是连续的,子序列则可以不必连续。

分析:我们借助于一个二维棋盘来进行分析。

 

利用该棋盘逐步就可以求得一直到两个字符串的末尾时的最大子串的长度。

可以得到;

棋盘用数组s[i][j]表示,Xi,Yj表示字符串的第i、j个字符。

当i或j等于0时,s[i][j]=0;

状态转移方程是,

如果Xi==Yj,s[i][j]=max(s[i-1][j],s[i][j-1])+1;

如果Xi!=Yj,s[i][j]=max(s[i-1][j],s[i][j-1]);

代码;

public class LCS {

    private static int fun(String s1,String s2) {

       int[][]dp=new int[s1.length()+1][s2.length()+1];

       //初始化边缘部分

       for (int i = 0; i < dp.length; i++)

           dp[i][0]=0;

       for (int j = 0; j < dp[0].length; j++)

           dp[0][j]=0;

       //状态转移运算

       for (int i = 0; i < s1.length(); i++) {

           for (int j = 0; j < s2.length(); j++) {

              if(s1.charAt(i)==s2.charAt(j))

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

              else dp[i+1][j+1]=dp[i+1][j]>dp[i][j+1]?dp[i+1][j]:dp[i][j+1];

           }

       }

       return dp[s1.length()][s2.length()];

    }

    //数据测试

    public static void main(String[] args) {

       String s1="123qwer",s2="123werwer";

       int num=fun(s1, s2);

       System.out.println(num);

    }

}

                                                                                                         --------亓慧杰                           

上一篇:没有了 下一篇:【韦德体育】如登陆不用去关心怎么判断用户存在否,可以看到是把用户的信息存入到了user这个javabean中

更多阅读

【韦德体育】如登陆不用去关心怎么判断

基础 2020-01-28
回想2007年1月的时候做的一个JSF的项目,那时候在网上找一个简单的例子,结果搜来搜去,都是...
查看全文

∩)o...)我就是这么wa了一次,线性动态规

基础 2020-01-28
动态规划: To The Max 线性动态规划   不要想当然的以为最小值就是0,(o(∩_∩)o...)我就是这...
查看全文

韦德体育只把相应的函数修改一下就可以

基础 2020-01-28
1./*使用return从函数中返回一个值*/ #includestdio.h int f1(int x,int y)    {     returnxy?x:y;/*条件表达...
查看全文

友情链接: 网站地图

Copyright © 2015-2019 http://www.koi-bumi.com. 韦德体育有限公司 版权所有