注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

和申的个人主页

专注于java开发,1985wanggang

 
 
 

日志

 
 

石子合并--动态规划--代码  

2008-10-27 09:51:28|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

石子合并--动态规划--代码 - 和申 - 和申的个人主页

对于这个问题是采用所谓动态归化动态规划的逆向思维法

要点可归纳为以下三个步骤:
  (1)分析最优值的结构,刻画其结构特征;
  (2)递归地定义最优值;
  (3)按自底向上或自顶向下记忆化的方式计算最优值。

本题分析一下,如堆的数量是,4,1,3

那么分数最高的是4,3合并,(4+3),1合并(是环形)

分数最低的是1,3合并,(1+3),4合并

我用java写的程序但为了便于转化为C/C++没有采用java特有的语法,采用数组保存结果,每次shift后即得合并后的状态,sum返回相邻的和,然后求出每次合并前,最优的方法的索引,进行合并

/**
 * 求分数最大
 */
package dyna;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wanggang
 * @version Oct 20, 2008
 */
public class Dyna {

 /**
  * @param args
  * @throws IOException
  */
 public static void main(String[] args) throws IOException {
  // TODO Auto-generated method stub
  FileInputStream fis = new FileInputStream("input.txt");
  BufferedReader br = new BufferedReader(new InputStreamReader(fis));
  String strN = br.readLine();
  String strHeap = br.readLine();
  br.close();
  
  int N = Integer.parseInt(strN);
  String[] strHeaps = strHeap.split(" ");
  int[] heaps = new int[N];
  for(int i=0;i<N;i++){
   heaps[i] = Integer.parseInt(strHeaps[i]);//init
  }
  System.out.println("-----------------------------------");
  for(int i=0;i<heaps.length;i++){
    System.out.print(heaps[i]+":");
  }
  System.out.println();
  System.out.println("-----------------------------------");
  long mark=0;
  
  int  m = N;//m 为的第n轮的堆数
  int index =0;
  int bestIndex=0;
  long maxNum=-1;
  long sum=0;
  for(;m>1;m--){
   
   for(index=0;index<m;index++){
    sum = sum(m,heaps, index);
    if(maxNum<sum){
     maxNum = sum;
     bestIndex = index;
     System.out.println(maxNum+"bestIndex"+bestIndex);
    }
   }
   shift(m,heaps,bestIndex);
   System.out.println("maxNum:"+maxNum);
   mark += maxNum;
   
   bestIndex=0;
   maxNum=-1;
  }
  
  
  System.out.println("Mark:"+mark);
  
  
 }
 
 public static long sum(int m,int[] heaps,int index){//index为0开始,直到本伦比较结束
  if(m == 1) return heaps[0];
  else if(index == (m -1)){
   return heaps[index]+heaps[0];
  }
  
  return heaps[index]+heaps[index+1];
 }
 
 public static void shift(int m,int[]heaps,int index){
  if(index == m-1){
   heaps[0]=heaps[0]+heaps[index];
  }else{
   heaps[index] = heaps[index]+heaps[index+1];
   int i= index+1;
   while(i<m-1){
    
    heaps[i] = heaps[i+1];
    i++;
   };
  }
  System.out.println("-----------------------------------");
  for(int i=0;i<m;i++){
    System.out.print(heaps[i]+":");
  }
  System.out.println();
  System.out.println("-----------------------------------");
 }


}

---------------------------------------------- 
/**
 * 求分数最小
 */
package dyna;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wanggang
 * @version Oct 20, 2008
 */
public class DynaMin {

 /**
  * @param args
  * @throws IOException
  */
 public static void main(String[] args) throws IOException {
  // TODO Auto-generated method stub
  FileInputStream fis = new FileInputStream("input.txt");
  BufferedReader br = new BufferedReader(new InputStreamReader(fis));
  String strN = br.readLine();
  String strHeap = br.readLine();
  br.close();
  
  int N = Integer.parseInt(strN);
  String[] strHeaps = strHeap.split(" ");
  int[] heaps = new int[N];
  for(int i=0;i<N;i++){
   heaps[i] = Integer.parseInt(strHeaps[i]);//init
  }
  System.out.println("-----------------------------------");
  for(int i=0;i<heaps.length;i++){
    System.out.print(heaps[i]+":");
  }
  System.out.println();
  System.out.println("-----------------------------------");
  long mark=0;
  
  int  m = N;//m 为的第n轮的堆数
  int index =0;
  int bestIndex=0;
  long minNum=Long.MAX_VALUE;
  long sum=0;
  for(;m>1;m--){
   
   for(index=0;index<m;index++){
    sum = sum(m,heaps, index);
    if(minNum>sum){
     minNum = sum;
     bestIndex = index;
     System.out.println(minNum+"bestIndex"+bestIndex);
    }
   }
   shift(m,heaps,bestIndex);
   System.out.println("minNum:"+minNum);
   mark += minNum;
   
   bestIndex=0;
   minNum=Long.MAX_VALUE;
  }
  
  
  System.out.println("Mark:"+mark);
  
  
 }
 
 public static long sum(int m,int[] heaps,int index){//index为0开始,直到本伦比较结束
  if(m == 1) return heaps[0];
  else if(index == (m -1)){
   return heaps[index]+heaps[0];
  }
  
  return heaps[index]+heaps[index+1];
 }
 
 public static void shift(int m,int[]heaps,int index){
  if(index == m-1){
   heaps[0]=heaps[0]+heaps[index];
  }else{
   heaps[index] = heaps[index]+heaps[index+1];
   int i= index+1;
   while(i<m-1){
    
    heaps[i] = heaps[i+1];
    i++;
   };
  }
  System.out.println("-----------------------------------");
  for(int i=0;i<m;i++){
    System.out.print(heaps[i]+":");
  }
  System.out.println();
  System.out.println("-----------------------------------");
 }


}

---------------------------------------------------------------------------------------------------------------------------------
//C++代码

#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

 

long sum(int m,int heaps[],int index)//求出相邻的堆合并的总数
{         
     if(index ==(m-1))//如果是最后一个,合数组的第一个无素合并,将数组首尾相加,模拟环
     {
              return heaps[index]+heaps[0];
     }
     return heaps[index]+heaps[index+1]; //当前位置和下一个位置的和
}

void shift(int m,int heaps[],int index)//合并指定 的相邻的两个堆
{
       if(index == m-1)
       {
                heaps[0] = heaps[0]+heaps[index];
       }else
       {
            heaps[index] = heaps[index]+heaps[index+1];
            int i = index +1;
            while(i<m-1)
            {
                        heaps[i] = heaps[i+1];
                        i++;
            }
       }
       cout<<"after merge"<<endl<<"heaps ";
       for(int i=0;i<m-1;i++)
       {
            cout<<heaps[i]<<" ";       
       }
       cout<<endl;  
}

int main(int argc, char *argv[])
{
    int n;//
  
    string file_name="c:\\input.txt";
    ifstream fin(file_name.c_str());
    if(!fin){
  cerr<<"Error ,to open file "<<file_name<<endl;
   system("PAUSE");
  return -1;
 }
 string temp="";
    getline(fin,temp);
    n= atoi(temp.c_str());
    cout<<" Input.txt"<<endl;
    cout<<"n="<<n<<endl;
    int heaps[n];
    
    for(int i=0;i<n;i++){
          
            fin>>temp;
            heaps[i]=atoi(temp.c_str());
    }
    for(int i=0;i<n;i++)
    {
            cout<<heaps[i]<<" ";       
           
    }
    cout<<endl;
    cout<<"--------------------------------------"<<endl;
    long mark=0;
    int m =n;//m为第n次合并后的堆数
    int index =0;//当前的标识堆的位置(0 ---- n-1)
    int bestIndex = 0;//最好的合并的位置
    long maxNum = -1;
    long sumValue =0;
    for(;m>1;m--)
    {
       
            for(index=0;index<m;index++){
    sumValue = sum(m,heaps, index);
    cout<<"sumValue"<<sumValue<<endl;
    if(maxNum<sumValue){
     maxNum = sumValue;
     bestIndex = index;
     cout<<"index "<<index<<endl;
    }
    
   }
   cout<<"this time bestIndex:"<<bestIndex;
   cout<<" and  maxNum:"<<maxNum<<endl;
   shift(m,heaps,bestIndex);
  
   mark += maxNum;
   
   bestIndex=0;
   maxNum=-1;  
   cout<<"--------------------------------------"<<endl;
    }
    cout <<"total mark is "<<mark<<endl;
    cout<<"hello"<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

统计信息唧唧歪歪唧唧网ggyygg.net
  评论这张
 
阅读(1391)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016