首页 > 编程语言 >算法设计与分析

算法设计与分析

时间：2024-06-08 16:31:58浏览次数：26  
标签：分析 weight int void ++ 算法 设计 100 节点

算法设计与分析

分治法

基本思想

将一个较难解决的问题，分割成一些小规模的子问题，逐个击破，分而治之。

1）该问题的规模缩小到一定程度就可以容易的解决；

2）该问题可以分解成若干个规模较小的性质相同的子问题，也称该问题具有最优子结构性质；

时间复杂度

T ( n ) = { k T ( n / m ) + f ( n ) , n > 1 ; O ( 1 ) , n = 1 ; T(n)= \begin{cases} kT(n/m)+f(n),n>1;\\ O(1),n=1; \end{cases} T(n)={kT(n/m)+f(n),n>1;O(1),n=1;​

使用迭代法求解

T(n)=kT(n/m)+f(n)
    =k{kT(n/m^2)+f(n/m)}+f(n)
    =k^2T(n/m^2)+f(n/m)+f(n)
    .....
    =

T ( n ) = n l o g m k + ∑ j = 0 l o g m n − 1 k j f ( n / m j ) T(n)=n^{log_mk}+\sum_{j=0}^{log_mn-1}k^jf(n/m^j) T(n)=nlogm​k+j=0∑logm​n−1​kjf(n/mj)

二分搜索
寻找假币
int FalseCoin(int coin[],int low,int high){
  if(low+1==high){
    if(coin[low]<coin[high])  return low+1;
    return high+1;
  }
  int sum1=0,sum2=0,sum3=0;
  int mid=(low+high)/2>>1;
  int i;
  //偶数个硬币
  if((high-low+1)%2==0){
    //左边
    for(i=low;i<=mid;i++){
      sum1+=coin[i];
    }
    //右边
    for(i=mid+1;i<=high;i++){
      sum2+=coin[i];
    }
    if(sum1>sum2){
      return FalseCoin(coin,mid+1,high);
    }else if(sum1<sum2){
       return FalseCoin(coin,low,mid);
    }else{
      return -1;
    }
  }else{
     for(i=low;i<=mid;i++){  //左边，去掉中间一个硬币
       sum1+=coin[i];
     }
     for(i=mid+1;i<high;i++){
       sum2+=coin[i];
     }
     sum3=coin[mid];
     if(sum1>sum2){
       return FalseCoin(coin,mid+1,high);
     }else if(sum1<sum2){
       return FalseCoin(coin,low,mid-1);
     }else{  //中间是假币
       if(coin[mid]!=coin[low]){
         return mid+1;
       }else{ return -1;
       }
     }
  }
 return -1; 
}

二分搜索算法描述

给定的序列已经按升序或降序排列完；

template<class Type>
int BinarySearch(Type a[],const Type &x,int left,int right){
  while(right>=1){
    int m=(left+right)/2;
    if(x==a[m]){
      return m;
    }
    if(a<a[m]){
      right=m-1;
    }esle{
     left=m+1;
    }
  }
}
棋盘覆盖
#include<iostream>
using namespace std;

int def[110][110];
static int t = 0;

void chess(int a, int b, int aa, int bb, int length) {
	if(length==1) return;
	t++;
	int tem = t;
	int l = length/2;
	if(aa<a+l && bb<b+l) chess(a,b,aa,bb,l);
	else {
		def[a+l-1][b+l-1] = tem;
		chess(a,b,a+l-1,b+l-1,l);
	}
	
	if(aa>=a+l && bb<b+l) chess(a+l,b,aa,bb,l);	//左下角棋盘
	else {
		def[a+l][b+l-1]=tem;
		chess(a+l,b,a+l,b+l-1,l);
	} 
	
	if(aa<a+l && bb>=b+l) chess(a,b+l,aa,bb,l);	//右上角的子棋盘
	else {
		def[a+l-1][b+l] = tem;
		chess(a,b+l,a+l-1,b+l,l);
	} 
	
	if(aa>=a+l && bb>=b+l) chess(a+l, b+l, aa, bb,l);
	else {
		def[a+l][b+l]=tem;
		chess(a+l, b+l, a+l, b+l, l);
	}
} 

int main() {
	int n, a, b, aa, bb, length, m;
	//a,b 是子棋盘左上角的行列号
	//aa,bb是特殊点的行列号
	cin>>length>>aa>>bb;
	a = b = 1;
	m = length;
	
	chess(a,b,aa,bb,length); 
	
	for(int i=1;i<=m;i++) //输出结果
        for(int j=1;j<=m;j++){
            cout.width(3);
            cout<<def[i][j];
            if(j==m) cout<<endl;
        }
	return 0;
}
合并排序(递归排序)

1)分解:将n个元素分成各含n/2个元素的子序列;

2)递归求解:用合并排序法将二个子序列继续进行分解和递归排序;

3)合并:合并已有的两个子序列；

template<class Type>
void MergeSort(Type a[],int left,int right){
  if(left<right){
    int i=(left+right)/2;
    MergeSort(a,left,i);
    MergeSort(i,i+1,right);
    merge(a,b,left,i,right); //合并到数组b
    copy(a,b,left,right); //复制回数组a
  }
}

void Merge(int Array[], int begin, int middle, int end){
	int n1 = middle - begin;
	int n2 = end - middle;
	
	int *left = new int[n1];
	int *right = new int[n2];
	
	for(int i = 0; i < n1; i++)
		left[i] = Array[begin + i];    
	for(int i = 0; i < n2; i++)
		right[i] = Array[middle + i];  
	
 
	int i = 0, j = 0, key;
	for(key = begin; key < end; key++){
		if(i < n1 && left[i] <= right[j])
			Array[key] = left[i++];
		
		else if(j < n2 && left[i] >= right[j])
			Array[key] = right[j++];
		
		else if(i == n1 && j < n2){
			Array[key] = right[j++];
		}
			
		else if(j == n2 && i < n1){
			Array[key] = left[i++];
		}	
			
	}
}
快速排序
循环赛日程表

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

template<class Type>
void Table(int k){
    int i,j,n,t,temp;
    n=2;
    a[1][1]=1;
    a[1][2]=2;
    a[1][3]=3;
    a[1][4]=4;
    for(t=1;t<k;t++){
        temp=n;
        n=n*2;
        //左上角
        for(i=temp+1;i<=n;i++){
            for(j=1;j<=temp;j++){
                a[i][j]=a[i-temp][j]+temp;
            }
        }
        //右上角
        for(i=1;i<=temp;i++){
            for(j=temp+1;j<=n;j++){
                a[i][j]=a[i+temp][(j+temp)%n];
            }
        }
        //右下角
        for(i=temp+1;i<=n;i++){
            for(j=temp+1;j<=n;j++){
                a[i][j]=a[i-temp][j-temp];
            }
        }
    }
}

动态规划

引言

对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的求解过程依赖于前一阶段的求解结果，动态规划就是将这种多阶段求解问题进行公式化的一种方法。

矩阵连乘问题
题目

矩阵连乘问题的定义
输入：n个矩阵A1,A2,…,An，其中Ai的维数为pi-1×pi
Ai 和Ai+1是可乘的

输出：连乘积A1A2A3…An

优化目标：最小计算代价（最优的计算次序）

矩阵乘法的代价：乘法次数
若A 是p ×q 矩阵，B 是q ×r 矩阵，则A ×B 的代价是pqr
因为矩阵乘法满足结合律，因此矩阵连乘可以由不同的计算次序，这种计算次序可以用加括号来表示。

三个矩阵A1: 10×100, A2: 100×5，A3: 5×50
(A1A2)A3
代价：10×100×5＋10×5×50＝7500
A1(A2A3)
代价：100×5×50＋10×100×50＝75000

三个矩阵A1: 10×100, A2: 100×5，A3: 5×50
(A1A2)A3
代价：10×100×5＋10×5×50＝7500
A1(A2A3)
代价：100×5×50＋10×100×50＝75000

可见不同的计算次序会导致不同的计算代价，我们要做的就是让这个代价最小。

分析最优解结构
设计算A[i:j]（矩阵A从i乘到j），1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]。

  当i=j时，A[i:j]=Ai，因此，m[i][i]=0，i=1,2,…,n
  当i<j时，若A[i:j]的最优次序在Ak和Ak+1之间断开，i<=k<j,则：m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj。由于在计算是并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i个可能。因此，k是这j-i个位置使计算量达到最小的那个位置。

建立的递归关系就是

计算A[i:j]所需的最小乘法次数为m（i，j）
m ( i , j ) = { 0 , i = j m i n { m ( i , k ) + m ( k + 1 , j ) + p i − 1 p k p j } , i < j m(i,j)= \begin{cases} 0,i=j\\ min\{m(i,k)+m(k+1,j)+p_{i-1}p_kp_j \},i<j \end{cases} m(i,j)={0,i=jmin{m(i,k)+m(k+1,j)+pi−1​pk​pj​},i<j​
其中Ai是Pi-1和Pi的矩阵

A1A2A3A4A5A6
30*5035*1515*55*1010*2020*25
i，j123456
1015750787593751187515125
2025254375712510500
3075025005375
4010003500
505000
60

继续构造

m(1,2)=min{m (1,1) +m(2,2) +p0p1p2}={0+0+303515}=15750

m(2,3)=min(m(2,2)+m(3,3)+p1p2p3)=2625

在这里插入图片描述
在这里插入图片描述

代码
#include<iostream>
using namespace std;
const int N = 100;
int A[N];//矩阵规模
int m[N][N];//最优解
int s[N][N];
void MatrixChain(int n)
{
	int r, i, j, k;
	for (i = 0; i <= n; i++)//初始化对角线
	{
		m[i][i] = 0;
	}
	for (r = 2; r <= n; r++)//r个矩阵连乘
	{
		for (i = 1; i <= n - r + 1; i++)//r个矩阵的r-1个空隙中依次测试最优点
		{
			j = i + r - 1;
			m[i][j] = m[i][i]+m[i + 1][j] + A[i - 1] * A[i] * A[j];
			s[i][j] = i;
			for (k = i + 1; k < j; k++)//变换分隔位置，逐一测试
			{
				int t = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];
				if (t < m[i][j])//如果变换后的位置更优，则替换原来的分隔方法。
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}
void print(int i, int j)
{
	if (i == j)
	{
		cout << "A[" << i << "]";
		return;
	}
	cout << "(";
	print(i, s[i][j]);
	print(s[i][j] + 1, j);//递归1到s[1][j]
	cout << ")";
}
int main()
{
	int n;//n个矩阵
	cin >> n;
	int i, j;
	for (i = 0; i <= n; i++)
	{
		cin >> A[i];
	}
	MatrixChain(n);
	cout << "最佳添加括号的方式为：";
	print(1, n);
	cout << "\n最小计算量的值为：" << m[1][n] << endl;
	return 0;
}
备忘录方法

备忘录方法是对动态规划算法的变形，通过分治思想对原问题进行分解，仍然采用递归算法求解。区别在于备忘录为每一个子问题建立了备忘录，把解过的子问题存起来，需要时查看。

#include<iostream>
using namespace std;
 
#define N 7  //N为7，实际表示有6个矩阵
int p[N]={30,35,15,5,10,20,25};
int m[N][N],s[N][N];
int LookupChain(int i, int j){
    if(m[i][j]>0)
        return m[i][j];
    if(i == j)
        return 0;
    m[i][j] = LookupChain(i,i) + LookupChain(i+1,j)+p[i-1]*p[i]*p[j];
    s[i][j] = i;
    for(int k=i+1; k<j;k++){
        int t = LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];
        if(t<m[i][j]){
            m[i][j]=t;
            s[i][j]=k;
        }
    }
    return m[i][j];
}
 
int MemorizedMatrixChain(int n, int m[][N], int s[][N]){
    for(int i=1;i<=n;i++){  //初始化默认都是0
        for(int j=1;j<=n;j++)
            m[i][j] = 0;
    }
    return LookupChain(1,n);
}
/*
*追踪函数：根据输入的i,j限定需要获取的矩阵链的始末位置，s存储断链点
*/
void Traceback(int i,int j, int s[][N]){
    if(i==j)       //回归条件
    {
        cout<<"A"<<i;
    }
    else       //按照最佳断点一分为二，接着继续递归
    {
        cout<<"(";
        Traceback(i,s[i][j],s);
        Traceback(s[i][j]+1,j,s);
        cout<<")";
    }
}
int main(){
 
 
	MemorizedMatrixChain(N-1,m,s);//N-1因为只有六个矩阵
    Traceback(1,6,s);
	return 0;
}
最长公共子序列
递归公式

c [ i ] [ j ] = { 0 , i = 0 , j = 0 ; c [ i − 1 ] c [ j − 1 ] + 1 , i , j > 0 ; x i = y j ; m a x { c [ i ] [ j − 1 ] , c [ i − 1 ] [ j ] , i , j > 0 ; x i ≠ y j } c[i][j]= \begin{cases} 0,i=0,j=0;\\ c[i-1]c[j-1]+1,i,j>0;x_i=y_j;\\ max\{c[i][j-1],c[i-1][j],i,j>0;x_i\neq y_j\} \end{cases} c[i][j]=⎩ ⎨ ⎧​0,i=0,j=0;c[i−1]c[j−1]+1,i,j>0;xi​=yj​;max{c[i][j−1],c[i−1][j],i,j>0;xi​=yj​}​

计算最优值
template<class Type>
void LCSLength(int m,int n,char *x,char *y,int **c){
  int i,j;
  for(i=1;i<=m;i++){
    c[i][0]=0;
  }
  for(i=1;i<=n;i++){
    c[0][i]=0;
  }
  for(i=1;i<=m;i++){
    for(j=1;j<=n;j++){
      if(x[i]==y[j]){
        c[i][j]=c[i-1][j-1]+1;
      }else{
        if(c[i-1][j]>=c[i][j-1]){
          c[i][j]=c[i-1][j];
        }else{
          c[i][j]=c[i][j-1]   //c[i][j]记录序列X与Y的最长公共子序列的长度
        }
      }
    }
  }
}
构造最长公共子序列

用数组b(i,j)记录c(i,j)的值是由那种子问题求得，b(i,j)表示在计算过程中的搜索状态，主要用于构造最长公共子序列。

template<class Type>
void LCSLength(int m,int n,char *x,char *y,int **c,int **b){
  int i,j;
  for(i=1;i<=m;i++){
    c[i][0]=0;
  }
  for(i=1;i<=n;i++){
    c[0][i]=0;
  }
  for(i=1;i<=m;i++){
    for(j=1;j<=n;j++){
      if(x[i]==y[j]){
        c[i][j]=c[i-1][j-1]+1;
        b[i][j]=1; //在尾部加上Xi=Yi,下一个搜索方向是b[i-1][j-1],输出Xi
      }else{
        if(c[i-1][j]>=c[i][j-1]){
          c[i][j]=c[i-1][j];
          b[i][j]=2; //下一个搜索方向是b[i-1][j]
        }else{
          c[i][j]=c[i][j-1];   //c[i][j]记录序列X与Y的最长公共子序列的长度
          b[i][j]=3; //搜索方向b[i][j]
        }
      }
    }
  }
}

template<class Type>
void LCS(int i,int j,char *x,int **b){
  if(i==0||j==0){
    return 0;
  }
  if(b[i][j]==1){
    LCS(i-1,j-1,x,b);
    cout<<x[i];
  }else{
    if(b[i][j]==2){
      LCS(i-1,j,x,b);
    }else{
      LCS(i,j-1,x,b);
    }
  }
}
改进算法
template<class Type>
void LCSLength(int m,int n,char *x,char *y,int **c,int **b){
  int i,j;
  for(i=1;i<=m;i++){
    c[i][0]=0;
  }
  for(i=1;i<=n;i++){
    c[0][i]=0;
  }
  for(i=1;i<=m;i++){
    for(j=1;j<=n;j++){
      if(x[i]==y[j]){
        c[i][j]=c[i-1][j-1]+1;
        b[i][j]=1; //在尾部加上Xi=Yi,下一个搜索方向是b[i-1][j-1],输出Xi
      }else{
        if(c[i-1][j]>c[i][j-1]){
          c[i][j]=c[i-1][j];
          b[i][j]=2; //下一个搜索方向是b[i-1][j]
        }else{
          if(c[i-1][j]<c[i][j-1]){
            c[i][j]=c[i][j-1];
            b[i][j]=3;
          }else{
            c[i][j]=c[i-1][j];
            b[i][j]=4;
          }
        }
      }
    }
  }
}

template<class Type>
void LCS(int i,int j,char *x,int **b){
  if(i==0||j==0){
    return 0;
  }
  if(b[i][j]==1){
    LCS(i-1,j-1,x,b);
    cout<<x[i];
  }else{
    if(b[i][j]==2){
      LCS(i-1,j,x,b);
    }else{
      if(b[i][j]==3){
          LCS(i,j-1,x,b);
      }else{
          LCS(i-1,j,x,b);
          LCS(i,j-1,x,b);
      }
    }
  }
}
最大子段和
#include<iostream>
using namespace std;

int maxSum(int a[], int n){
	
	int sum = 0;
	int b = 0;
	
	for(int i = 0; i < n; i++){
		
		if(b > 0)
			b += a[i]；	
		else
			b = a[i];
		
		if(b > sum)
			sum = b;
	}
	return sum;	
}

int main(){
	
	int a[] = {-2,11,-4,13,-5,-2,6};

	for(int i= 0; i < 7; i++)
	{
		cout<<a[i]<<" ";
	}	 
	cout<<endl;
	cout<<"数组a的最大连续子段和为：" << maxSum(a, 7)<<endl;
	return 0;
}
0-1背包问题
题目：

一个背包，背包容量capacity=8。有7个物品，物品可以分割成任意大小。要求尽可能的装入背包中物品总价值最大，但不能超过总容量。

i(物品编号)1234
w(体积)2345
v(价值)3456
解题步骤

Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。

1、建立模型，即求max(V1X1+V2X2+…+VnXn)；

2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；

3、寻找递推关系式，面对当前商品有两种可能性：

包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。
其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；

由此可以得出递推关系式：

V ( i , j ) = { V ( i − 1 , j ) , j < w ( i ) ; m a x { V ( i − 1 , j ) , V ( i − 1 , j − w ( i ) + v ( i ) ) } , j > = w ( i ) V(i,j)= \begin{cases} V(i-1,j),j<w(i);\\ max\{V(i-1,j),V(i-1,j-w(i)+v(i))\},j>=w(i) \end{cases} V(i,j)={V(i−1,j),j<w(i);max{V(i−1,j),V(i−1,j−w(i)+v(i))},j>=w(i)​

i/j012345678
0000000000
1003333333
2003447777
3003457899
40034578910
#include<iostream>
using namespace std;
#include <algorithm>
 
int main()
{
	int w[5] = { 0 , 2 , 3 , 4 , 5 };	//商品的体积2、3、4、5
	int v[5] = { 0 , 3 , 4 , 5 , 6 };	//商品的价值3、4、5、6
	int bagV = 8;					    //背包大小
	int dp[5][9] = { { 0 } };			    //动态规划表
 
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= bagV; j++) {
			if (j < w[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
 
	//动态规划表的输出
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 9; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}
 
	return 0;
}

贪心算法

引言

贪心算法求解问题时不从整体最优考虑，所做出的选择只是在某种意义上局部最优的选择。

活动安排问题
问题描述和分析

​ 设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。

活动安排问题： 要在所给的活动集合中选出最大的相容活动子集合。

活动安排问题的关键是如何按照一定的顺序安排活动，使得选出的活动间相容并能安排尽量多的活动。

设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：

i1234567891011
S[i]130535688212
f[i]4567891011121314
核心代码
int cnt=1;
int temp=t[0].end;
for(int i=1;i<N;i++){
  if(t[i].begin>=temp){
    cnt++;
    temp=t[i].end;
  }
}
代码
#include<iostream>
using namespace std;
 
int s[12]={0,1,3,0,5,3,5,6,8,8,2,12},f[12]={0,4,5,6,7,8,9,10,11,12,13,14};
bool a[11];
int n=11;
int Selector()
{
    a[1]=true;
    int j=1;
    int count=1;
    for (int i=2;i<=n;i++) 
	{
		if(s[i]>=f[j]) 
		{   
			a[i]=true;   
			j=i;     
			count++;          
		}
        else 
			a[i]=false;
	}
	return count;
}
 
int main()
{
	cout<<"活动序号："<<endl;
	for(int i=1;i<=11;i++)
		cout<<i<<" ";
	cout<<endl<<"活动开始时间："<<endl;
	for(int i=1;i<=11;i++)
		cout<<s[i]<<" ";
	cout<<endl<<"活动结束时间："<<endl;
	for(int i=1;i<=11;i++)
		cout<<f[i]<<" ";
	int count=Selector();
	cout<<endl<<"一共选择个"<<count<<"活动如下："<<endl;
	for(int i=0;i<=n;i++)
		if(a[i])
			cout<<i<<" ";
	return 0;
}
最优装载

贪心策略:重量最轻者先装

最优子结构性质: T(1,n,c)=1+T(2,n,c-w)

伪代码
void Loading(int n,int c,int *x,int *w){
   for(int i=1;i<=n;i++){
     x[i]=0; //初值为0
   }
   for(int i=1;i<=n&&w[i]<=c;i++){
     x[i]=1; //放到船上
     c-=w[i]; //船的容量减少
   }
}
背包问题
题目：

一个背包，背包容量M=150。有7个物品，物品可以分割成任意大小。要求尽可能的装入背包中物品总价值最大，但不能超过总容量。

物品ABCDEFG
重量35306050401025
价值10403050354030
解题步骤

首先计算每种物品单位重量的价值v[i]/w[i]，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。

代码
#include <iostream>
using namespace std;
//按照单位重量的价值量大小降序排列
void Sort(int n,float *w,float *v)
{
    int i,j;
    float temp1,temp2;
    for(i=1;i<=n;i++)
    for(j=1;j<=n-i;j++)//冒泡排序
    {
        temp1=v[j]/w[j];
        temp2=v[j+1]/w[j+1];
        if(temp1<temp2)
        {
            swap(w[j],w[j+1]);
            swap(v[j],v[j+1]);
        }
    }
}
int main()
{
    float w[101];//用来表示每个物品的重量
    float v[101];//用来表示每个物品的价值量
    float x[101];//表示最后放入背包的比例
    int n;//物品数
    float M;//背包最大容纳重量
    cin>>n>>M;
    //依次输入每件物品的重量和价值量
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    //按照单位重量的价值量大小降序排列
    Sort(n,w,v);
    int i;
    for(i=1;i<=n;i++)
        x[i]=0;//初始值，未装入背包，x[i]=0
    float c=M;//更新背包容纳量
    for(i=1;i<=n;i++)
    {
        if(c<w[i])  break;//不能完全装下
        x[i]=1;
        c=c-w[i];
    }
    if(i<=n)
        x[i]=c/w[i];
    //输出
    for(int i=1;i<=n;i++)
        cout<<"重量为"<<w[i]<<"价值量为"<<v[i]<<"的物品"<<"放入的比例为"<<x[i]<<endl;
    return 0;
}
哈夫曼编码
    include <iostream>
    using namespace std;
     
    //最大字符编码数组长度
    #define MAXCODELEN 100
    //最大哈夫曼节点结构体数组个数
    #define MAXHAFF 100
    //最大哈夫曼编码结构体数组的个数
    #define MAXCODE 100
    #define MAXWEIGHT  10000;
     
     
    typedef struct Haffman
    {
        //权重
        int weight;
        //字符
        char ch;
        //父节点
        int parent;
        //左儿子节点
        int leftChild;
        //右儿子节点
        int rightChild;
    }HaffmaNode;
     
    typedef struct Code
    {
        //字符的哈夫曼编码的存储
        int code[MAXCODELEN];
        //从哪个位置开始
        int start;
    }HaffmaCode;
     
    HaffmaNode haffman[MAXHAFF];
    HaffmaCode code[MAXCODE];
     
    void buildHaffman(int all)
    {
        //哈夫曼节点的初始化之前的工作, weight为0,parent,leftChile,rightChile都为-1
        for (int i = 0; i < all * 2 - 1; ++i)
        {
            haffman[i].weight = 0;
            haffman[i].parent = -1;
            haffman[i].leftChild = -1;
            haffman[i].rightChild = -1;
        }
        std::cout << "请输入需要哈夫曼编码的字符和权重大小" << std::endl;
        for (int i = 0; i < all; i++)
        {
            std::cout << "请分别输入第个" << i << "哈夫曼字符和权重" << std::endl;
            std::cin >> haffman[i].ch;
            std::cin >> haffman[i].weight;
        }
        //每次找出最小的权重的节点,生成新的节点,需要all - 1 次合并
        int x1, x2, w1, w2;
        for (int i = 0; i < all - 1; ++i)
        {
            x1 = x2 = -1;
            w1 = w2 = MAXWEIGHT;
            //注意这里每次是all + i次里面便利
            for (int j = 0; j < all + i; ++j)
            {
                //得到最小权重的节点
                if (haffman[j].parent == -1 && haffman[j].weight < w1)
                {
                    //如果每次最小的更新了，那么需要把上次最小的给第二个最小的
                    w2 = w1;
                    x2 = x1;
                    x1 = j;
                    w1 = haffman[j].weight;
                }
                //这里用else if而不是if,是因为它们每次只选1个就可以了。
                else if(haffman[j].parent == -1 && haffman[j].weight < w2)
                {
                    x2 = j;
                    w2 = haffman[j].weight;
                }
            }
            //么次找到最小的两个节点后要记得合并成一个新的节点
            haffman[all + i].leftChild = x1;
            haffman[all + i].rightChild = x2;
            haffman[all + i].weight = w1 + w2;
            haffman[x1].parent = all + i;
            haffman[x2].parent = all + i;
            std::cout << "x1 is" << x1 <<" x1 parent is"<<haffman[x1].parent<< " x2 is" << x2 <<" x2 parent is "<< haffman[x2].parent<< " new Node is " << all + i << "new weight is" << haffman[all + i].weight << std::endl;
        }
    }
    //打印每个字符的哈夫曼编码
    void printCode(int all)
    {
        //保存当前叶子节点的字符编码
        HaffmaCode hCode;
        //当前父节点
        int curParent;
        //下标和叶子节点的编号
        int c;
        //遍历的总次数
        for (int i = 0; i < all; ++i)
        {
            hCode.start = all - 1;
            c = i;
            curParent = haffman[i].parent;
            //遍历的条件是父节点不等于-1
            while (curParent != -1)
            {
                //我们先拿到父节点，然后判断左节点是否为当前值，如果是取节点0
                //否则取节点1,这里的c会变动，所以不要用i表示，我们用c保存当前变量i
                if (haffman[curParent].leftChild == c)
                {
                    hCode.code[hCode.start] = 0;
                    std::cout << "hCode.code[" << hCode.start << "] = 0" << std::endl;
                }
                else
                {
                    hCode.code[hCode.start] = 1;
                    std::cout << "hCode.code[" << hCode.start << "] = 1" << std::endl;
                }
                hCode.start--;
                c = curParent;
                curParent = haffman[c].parent;
            }
            //把当前的叶子节点信息保存到编码结构体里面
            for (int j = hCode.start + 1; j < all; ++j)
            {
                code[i].code[j] = hCode.code[j];
            }
            code[i].start = hCode.start;
        }
    }
    int main()
    {
        std::cout << "请输入有多少个哈夫曼字符" << std::endl;
        int all = 0;
        std::cin >> all;
        if (all <= 0)
        {
            std::cout << "您输入的个数有误" << std::endl;
            return -1;
        }
        buildHaffman(all);
        printCode(all);
        for (int i = 0; i < all; ++i)
        {
            std::cout << haffman[i].ch << ": Haffman Code is:";
            for (int j = code[i].start + 1; j < all; ++j)
            {
                std::cout << code[i].code[j];
            }
            std::cout << std::endl;
        }
        return 0;
    }

回溯法

基本思想
常用定义

问题的解向量:一个问题的解向量可以构成一个n元组的形式，这个n元组称为问题的解向量；

问题的解空间:问题的解是问题解空间的一个子集，解空间中满足所有约束条件的解称为可行解；解空间中所求解的目标函数的最大或最小的可行解称为最优解；

解空间树:将回溯法的搜索空间看作是树形结构，也称解空间树或者状态树；

回溯法的基本思想:在一棵含有全部问题解的状态空间树上进行深度优先搜索，从根节点出发搜索解空间树，解为叶子节点；

回溯法框架
递归回溯
template<class Type>
void backtrack(int t){
  if(t>n) output(x);
  else{
     for(int i=f(n,t);i<=g(n,t);i++){ //当前扩展结点处搜索过的子树起始编号和终止编号
       x[t]=h(i);
       if(Constraint(t)&&Bound(t)){ //约束条件与限界函数
         backtrack(t+1);
       }
     }
  }
}
迭代回溯
template<class Type>
void iteractiveBacktrack(){
  int t=1;
  while(t>0){
    if(f(n,t)<=g(n,t)){
       for(int i=f(n,t);i<=g(n,t);i++){
         x[t]=h(i);
         if(Constraint(t)&&Bound(t)){
           if(solution(t)) output(x);
           else t++;
         }
       }
    }
  }
}
子集树
template <class Type>
void backtrack(int t){
  if(t>n) output(x);
  else
    for(int i=0;i<=1;i++){
      x[t]=i;
      if(legal(t)){
        backtrack(t+1);
      }
    }
}
装载问题
问题描述:

有n个集装箱要装上2艘载重量分别为c1,c2的轮船,其中集装箱i的重量Wi,且

​
∑ i = 1 n w i ≤ c 1 + c 2 \sum_{i=1}^{n}{w_i}\leq{c_1+c_2} i=1∑n​wi​≤c1​+c2​

核心代码
void Backtrack(int i){
  if(i>=n){  //叶子节点
    bestw=cw;
    for(j=1;j<=n;j++){
     bestx[j]=x[j];
    }
    return;
  }
  if(cw+w[i]<=c){
    x[i]=1;
    cw+=w[i];
    Backtrack(i+1);
    cw-=w[i];
  }
  x[i]=0;
  Backtrack(i+1);
}
改进代码—增加上界函数

上界函数 cw+r<=bestw，即当前重量+剩余集装箱重量 比最佳重量还小，则可将当前节点的右子树减去；

template <class Type>
void Loading<Type>::Backtrack(int i){
   if(i>n){
     bestw=cw;
       for(j=1;j<=n;j++){
           bestx[j]=x[j];
       }
     return;
   }
   r-=w[i];  //r初值为总重量,一开始先把第i个物品的重量减去
   if(cw+w[i]<=c){
     x[i]=1; //装入
     cw+=w[i];
     Backtack(i+1);
     cw-=w[i];
   }
   if(cw+r>bestw){ //如果不装，最大可能重量比bestw还大
     x[i]=0;
     Backtrack(i+1);
   }
   r+=w[i]; //回溯回去把w[i]加回去
}
代码
#include <bits/stdc++.h>
using namespace std;
int n; //集装箱数
int cw; // 当前载重量, current weight
int bestw; //最优载重重量
int r;  //剩余集装箱重量
int c1; //第一艘轮船的载重量
int c2; //第二艘轮船的载重量
int x[100]; //当前解
int bestx[100]; //当前最优解
int w[100]; //集装箱重量数组
void OutPut()
{
    int restweight = 0;
    for(int i = 1; i <= n; ++i)
        if(bestx[i] == 0)
           restweight += w[i];
    if(restweight > c2)
        cout<<"不能装入"<<endl;
    else
    {
        cout<<"船1装入的货物为:";
        for(int i = 1; i <= n; ++i)
            if(bestx[i] == 1)
               cout<<" "<<i;
        cout<<endl<<"船2装入的货物为:";
        for(int i = 1; i <= n; ++i)
            if(bestx[i] != 1)
               cout<<" "<<i;

    }
}
void BackTrack(int i)
{
    if(i > n)
    {
        if(cw > bestw)
        {
            for(int i = 1; i <= n; ++i)
                bestx[i] = x[i];
            bestw = cw;
        }
        return;
    }
    r -= w[i];
    if(cw + w[i] <= c1) //约束条件
    {
        cw += w[i];
        x[i] = 1;
        BackTrack(i + 1);
        x[i] = 0;
        cw -= w[i];
    }
    if(cw + r > bestw) //限界函数
    {
        x[i] = 0;
        BackTrack(i + 1);
    }
    r += w[i];

}
void Initialize()
{
    bestw = 0;
    r = 0;
    cw = 0;
    for(int i = 1; i <= n; ++i)
        r += w[i];
}
void InPut()
{
    cout<<"请输入箱子个数：";
    cin>>n;

    cout<<"请输入两艘船的最大载重量：";
    cin>>c1>>c2;

    cout<<"请输入箱子的重量：";
    for(int i = 1; i <= n; ++i)
       cin>>w[i];

}
int main()
{
    InPut();
    Initialize();
    BackTrack(1);
    OutPut();
}
n后问题
问题描述：

在N×N格的国际象棋上摆放N个皇后，使其不能互相攻击，即不能处于同一列或同一行，也不能处在同一斜线上，请问有多少种摆法？

解决策略:

用n元组x[1:n]表示n后问题的解,x[i]表示皇后i放在第i行的第x[i]列。

核心代码:
int place(int k){
  for(j=1;j<k;j++){
    if((abs(k-j)==abs(x[j]-x[k]))||x[j]==x[k])
      return 0;
  }
  return 1;
}
void Backtrack(int t){
  if(t>n){ //找到一种合适情况
    sum++;
  }else{
    for(i=1;i<=n;i++){
       x[t]=i; //第t行的皇后在第i列
       if(place(t)) //看第t行的皇后行不行
           Backtrack(t+1);
    }
  }
}
代码:
//
//  main.cpp
//  BackTrack Solution of N-Queens Problem.
//
//  Created by Kang on 2020/7/2 at NJUPT.
//  Copyright © 2020 Kang. All rights reserved.
//

#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;

const int maxSize = 10;
int x[maxSize];

/**
 Judge if the Queen can be placed at (k, x[k]), if OK, return true.
 */
bool CanPlace(int k){
    for(int i = 0; i < k; ++i) {
        if(x[i] == x[k] || abs(i-k) == abs(x[i]-x[k]))
            return false;
    }
    return true;
}

void Print(int N){
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if(x[i] != j) {
                printf(" ");
            } else {
                printf("▇\n");
                break;
            }
        }
    }
    printf("---------\n");
}

/**
 k the current deepth( from 0 to n-1) in the Solution Space Tree
 */
int Recursive_BackTrack(int k, int N){
    int solutionCount = 0;
    
    if(k == N){
        Print(N);
        return 1;
    }
    
    for (int i = 0; i < N; ++i) {
        x[k] = i;
        if(CanPlace(k)){
            solutionCount += Recursive_BackTrack(k+1, N);
        }
    }
    return solutionCount;
}

int Iterated_BackTrack(int N){
    int solutionCount = 0, k = 0;       // 问题解的个数、当前层数
    
    for (int i = 0; i < maxSize; ++i) { // 将所有层中，所选子树(列)的初始值置为-1
        x[i] = -1;
    }
    
    while (k > -1) {     // 如果已经退回第0行前面，则结束遍历
        if(k == N){      // 如果已经超过最后一行，则打印路径并返回上一层
            Print(N);
            ++solutionCount;
            --k;
            continue;
        }
        
        if(++x[k] < N){  // 如果还有未访问的子节点，则选择这棵树的下一个子树
            if(CanPlace(k)){
                ++k;     // 如果当前位置可以摆放，则k自增，进入下一行的循环。
            } else {
                         // 如果当前位置不能摆放，则k不必动，直接进入下次循环。
            }
        } else {         // 子树已经全部搜索，返回上一层
            x[k] = -1;   // 注意，返回时要将子树进行复位。
            --k;
        }
    }
    
    return solutionCount;
}

int main(int argc, const char * argv[]) {
    int N;
    int count;
    
    printf("请输入皇后个数：");
    scanf("%d", &N);
    
    // count = Recursive_BackTrack(0, N);
    count = Iterated_BackTrack(N);
    
    cout<<"共有"<<count<<"种不同的解法。"<<endl;
    return 0;
}

分支限界法

分支限界法以广度优先或最大耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法的搜索过程中产生的活结点表具有先进先出的性质，其本质上是队列。

单源最短路径问题
装载问题
问题描述:

有n个集装箱要装上2艘载重量分别为c1,c2的轮船,其中集装箱i的重量Wi,且

​
∑ i = 1 n w i ≤ c 1 + c 2 \sum_{i=1}^{n}{w_i}\leq{c_1+c_2} i=1∑n​wi​≤c1​+c2​

基本思路:

1.首先将第一艘轮船尽可能的装满；

2.将剩余的集装箱上第二艘轮船。

队列式分支限界法

1.解装载问题的队列式分支限界法仅求出所要求的最优值，稍后进一步构造最优解；

2.首先检测当前扩展节点的左儿子节点是否为可行节点。如果是，则将其加入到活结点队列中；

3.然后，将右儿子节点加入到活结点队列中(右儿子节点一定是可行节点)。2个儿子节点都产生后，当前扩展结点被舍弃；

4.活结点队列中，队首元素被取出作为当前扩展结点；

5.活结点队列已空，算法终止。

例子

在这里插入图片描述

如 n=4,c1=12,w=[8,6,2,3]

在这里插入图片描述

伪代码
while(true){
    //左节点
    //wt=Ew+w[i]
    if(wt<=c1){
        if(wt>bestw) bestw=wt;
        if(i<=n) Q.add(wt);
    }
    //右节点
    if(Ew+r>bestw&&i<=n){
        Q.add(Ew);
    }
    Q.Delete(Ew);
    if(Ew==-1){
        if(Q.IsEmpty()) return bestw;
        Q.add(-1);
        Q.Delete(Ew);
        i++;
        r-=w[i];
    }
}
代码
#include <bits/stdc++.h>
using namespace std;
typedef struct QNode
{
    QNode *parent;
    int lchild;//左子树为1，右子树为0
    int weight;
}QNode;
int n;
int c;
int bestw;
int w[100];
int bestx[100];

void InPut()
{
    scanf("%d %d", &n, &c);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &w[i]);
}

//QNode *&bestE 的原因是 首先bestE是个地址， 其次引用为了赋值使用, 后边for循环中用到
void EnQueue(queue<QNode *> &q, int wt, int i, QNode *E, QNode *&bestE, int ch)
{
    if(i == n)
    {
        if(wt == bestw)
        {
            bestE = E;
            bestx[n] = ch;
            return;
        }
    }
    QNode *b;
    b = new QNode;
    b->weight = wt;
    b->lchild = ch;
    b->parent = E;
    q.push(b);
}
int MaxLoading()
{
    queue<QNode *>q;
    q.push(0);
    int i = 1;
    int Ew = 0, r = 0;
    bestw = 0;
    for(int j = 2; j <= n; ++j)
        r += w[j];
    QNode *E, *bestE; //bestE的作用是：结束while循环后，bestE指向最优解的叶子节点，然后通过bestE->parent找到装入了哪些物品。
    E = new QNode; //E这里作为一个中间量，连接parent和child
    E = 0;         //赋0是因为树的根的值是0，while刚开始的时候其代表root
    while(true)
    {
        int wt = Ew + w[i];
        if(wt <= c)
        {
            if(wt > bestw)   //提前更新bestW,注意更新条件
                bestw = wt;
            EnQueue(q, wt, i, E, bestE, 1);
        }
        if(Ew + r >= bestw)   //右儿子剪枝
        {
            EnQueue(q, Ew, i, E, bestE, 0);    
        }
        E = q.front();
        q.pop();
        if(!E)    //如果取得的数是0，代表该处理下一层
        {
            if(q.empty())   //如果队列为空，表示该循环结束了
                break;
            q.push(0);     //如果队列中还有数据，表示循环还没结束。在该层的末尾加一个0标识符
            E = q.front();
            q.pop();
            i++;     //下一层走起
            r -= w[i];   //计算剩余的重量
        }
        Ew = E->weight; //不要忘记更新最新节点的值
    }
    for(int j = n - 1; j > 0; --j)
    {
        bestx[j] = bestE->lchild;
        bestE = bestE->parent;
    }
}
void OutPut()
{
    printf("最优装载量为 %d\n", bestw);
    printf("装载的物品为 \n");
    for(int i = 1; i <= n; ++i)
        if(bestx[i] == 1)
          printf("%d ", i);
}
int main()
{
    InPut();
    MaxLoading();
    OutPut();
}
优先队列式分支限界法

1.解装载问题的优先队列式分支界限法用最大优先队列存储活结点表；

2.活结点x在优先队列的优先级定义为从根节点到节点x的路径所相应的载重量Ew+剩余集装箱的重量r之和(上界Ew+r定义为节点优先级);

3.优先队列中优先级最大的活结点成为下一个扩展结点；

4.子集树中叶节点所相应的载重量与其优先级(上界值相同)

5.在优先队列式分支界限法中，一旦有一个叶节点成为当前扩展节点，则可以断言该叶节点所对应的解为最优解，即可终止算法；

在这里插入图片描述

代码
#include <bits/stdc++.h>
using namespace std;
class MaxHeapQNode
{
public:
    MaxHeapQNode *parent;  //父节点
    int lchild;    //左节点:1; 右节点"0
    int weight;    //总重量
    int lev;       //层次
};
struct cmp
{
    bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const
    {
        return a->weight < b->weight;
    }
};
int n;
int c;
int bestw;
int w[100];
int bestx[100];
void InPut()
{
    scanf("%d %d", &n, &c);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &w[i]);
}
void AddAliveNode(priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp> &q, MaxHeapQNode *E,  int wt, int i, int ch)
{
    MaxHeapQNode *p = new MaxHeapQNode;
    p->parent = E;
    p->lchild = ch;
    p->weight = wt;
    p->lev = i + 1;
    q.push(p);
}
void MaxLoading()
{
    priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp > q; // 大顶堆
    //定义剩余重量数组r
    int r[n + 1];
    r[n] = 0;
    for(int j = n - 1; j > 0; --j)
        r[j] = r[j + 1] + w[j + 1];
    int i = 1;
    MaxHeapQNode *E;
    int Ew = 0;
    while(i != n + 1)
    {
        if(Ew + w[i] <= c)
        {
            AddAliveNode(q, E, Ew + w[i] + r[i], i, 1);
        }
        AddAliveNode(q, E, Ew + r[i], i, 0);

        //取下一节点
        E = q.top();
        q.pop();
        i = E->lev;
        Ew = E->weight - r[i - 1];
    }
    bestw = Ew;
    for(int j = n; j > 0; --j)
    {
        bestx[j] = E->lchild;
        E = E->parent;
    }
}
void OutPut()
{
    printf("最优装载量为 %d\n", bestw);
    printf("装载的物品为 \n");
    for(int i = 1; i <= n; ++i)
        if(bestx[i] == 1)
          printf("%d ", i);
}
int main()
{
    InPut();
    MaxLoading();
    OutPut();
}
0-1背包问题
问题描述:

假设有4个物品，其重量分别为(4, 7, 5, 3)，价值分别为(40, 42, 25, 12)，背包容量W=10。将给定物品按单位重量价值从大到小排序

物品重量(w)价值(v)价值/重量(v/w)
144010
27426
35255
43124

在这里插入图片描述

上界函数
template<class Typew,class Typep>
Typep Knap<Typew,Typep>::Bound(int i){
   Typep cleft=c-cw;
   Typep b=cp;
   while(i<=n&&w[i]<=cleft){
    cleft-=w[i];
    b+=p[i];
    i++;
   }
   if(i<=n) b+=p[i]/w[i]*cleft;
   return b;
}
优先队列的分支界限法
#include <bits/stdc++.h>
using namespace std;
class Object
{
public:
    int id;
    int weight;
    int price;
    float d;
};
class MaxHeapQNode
{
public:
    MaxHeapQNode *parent;
    int lchild;
    int upprofit;
    int profit;
    int weight;
    int lev;
};
struct cmp
{
    bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const
    {
        return a->upprofit < b->upprofit;
    }
};
bool compare(const Object &a, const Object &b)
{
    return a.d >= b.d;
}
int n;
int c;
int cw;
int cp;
int bestp;
Object obj[100];
int bestx[100];
void InPut()
{
    scanf("%d %d", &n, &c);
    for(int i = 1; i <= n; ++i)
    {
     scanf("%d %d", &obj[i].price, &obj[i].weight);
     obj[i].id = i;
     obj[i].d = 1.0 * obj[i].price / obj[i].weight;
    }
 
    sort(obj + 1, obj + n + 1, compare);
//    for(int i = 1; i <= n; ++i)
//        cout << obj[i].d << " ";
//    cout << endl << "InPut Complete" << endl;
}
int Bound(int i)
{
    int tmp_cleft = c - cw;
    int tmp_cp = cp;
    while(tmp_cleft >= obj[i].weight && i <= n)
    {
        tmp_cleft -= obj[i].weight;
        tmp_cp += obj[i].price;
        i++;
    }
    if(i <= n)
    {
        tmp_cp += tmp_cleft * obj[i].d;
    }
    return tmp_cp;
}
void AddAliveNode(priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp> &q, MaxHeapQNode *E, int up, int wt, int curp, int i, int ch)
{
    MaxHeapQNode *p = new MaxHeapQNode;
    p->parent = E;
    p->lchild = ch;
    p->weight = wt;
    p->upprofit = up;
    p->profit = curp;
    p->lev = i + 1;
    q.push(p);
}
void MaxKnapsack()
{
    priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp > q; // 大顶堆
    MaxHeapQNode *E = NULL;
    cw = cp = bestp = 0;
    int i = 1;
    int up = Bound(1); //Bound(i)函数计算的是i还未处理时候的上限值
    while(i != n + 1)
    {
        int wt = cw + obj[i].weight;
        if(wt <= c)
        {
            if(bestp < cp + obj[i].price)
                bestp = cp + obj[i].price;
            AddAliveNode(q, E, up, cw + obj[i].weight, cp + obj[i].price, i, 1);
        }
        up = Bound(i + 1); //注意这里 up != up - obj[i].price而且 up >= up - obj[i].price
        if(up >= bestp) //注意这里必须是大于等于
        {
            AddAliveNode(q, E, up, cw, cp, i, 0);
        }
        E = q.top();
        q.pop();
        cw = E->weight;
        cp = E->profit;
        up = E->upprofit;
        i = E->lev;
    }
    for(int j = n; j > 0; --j)
    {
        bestx[obj[E->lev - 1].id] = E->lchild;
        E = E->parent;
    }
}
void OutPut()
{
    printf("最优装入量为 %d\n", bestp);
    printf("装入的物品为 \n");
    for(int i = 1; i <= n; ++i)
        if(bestx[i] == 1)
          printf("%d ", i);
}
int main()
{
    InPut();
    MaxKnapsack();
    OutPut();
}

标签：分析,weight,int,void,++,算法,设计,100,节点
From： https://blog.csdn.net/2301_82133855/article/details/139547477

相关文章

  • C++ 6.8笔记:①判断质数②二分基础算法
    质数试除法判定质数boolprimes(intx){  if(x<2)returnfalse;  for(inti=2;i<=x/i;i++){    if(x%i==0)returnfalse;  }  returntrue;}埃筛1intp[N],k,n;boolf[N];voidprimes(intn){//埃筛，思想：质数的倍数是合数for(inti......
  • 前端使用 Konva 实现可视化设计器（13）- 折线 - 最优路径应用【思路篇】
    这一章把直线连接改为折线连接，沿用原来连接点的关系信息。关于折线的计算，使用的是开源的AStar算法进行路径规划，启发方式为曼哈顿距离，且不允许对角线移动。请大家动动小手，给我一个免费的Star吧~大家如果发现了Bug，欢迎来提Issue哟~github源码gitee源码示例地址灵感......
  • 代码随想录算法训练营第五十一天| 121. 买卖股票的最佳时机、122.买卖股票的最佳时机I
    121.买卖股票的最佳时机一只股票只能买卖一次代码随想录.-力扣（LeetCode）输入：[7,1,5,3,6,4]输出：5解释：在第2天（股票价格=1）的时候买入，在第5天（股票价格=6）的时候卖出，最大利润=6-1=5。注意利润不能是7-1=6,因为卖出价格需要大于买入价格；同时，你不能在买入......
  • 代码随想录算法训练营第五十天| 198.打家劫舍、213.打家劫舍II、337.打家劫舍 III
    198.打家劫舍文档讲解：代码随想录题目链接：.-力扣（LeetCode） 问题：计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。也就是说相邻的房间不能偷当前房屋偷与不偷取决于前一个房屋和前两个房屋是否被偷了。所以这里就更感觉到，当前状态和前面状态会有一种依赖......
  • 数学模型：操作系统中FCFS、SJF、HRRN算法的平均周转时间比较 c语言
    摘 要研究目的：比较操作系统中进程调度FCFS、SJF、HRRN算法的平均周转时间和带权周转时间的大小关系。研究方法：在建模分析时，分别举4个进程的例子，1个进程用两个字母分别表示到达时间和执行时间。分两种极端情况，一种是每个进程到达时cpu还在执行之前的进程，这种结果为T(FCFS)>T......
  • 【计算机毕业设计】springboot287基于javaEE的校园二手书交易平台的设计与实现
    信息数据从传统到当代，是一直在变革当中，突如其来的互联网让传统的信息管理看到了革命性的曙光，因为传统信息管理从时效性，还是安全性，还是可操作性等各个方面来讲，遇到了互联网时代才发现能补上自古以来的短板，有效的提升管理的效率和业务水平。传统的管理模式，时间越久管理的内容......
  • 【计算机毕业设计】springboot283图书商城管理系统
    现代经济快节奏发展以及不断完善升级的信息化技术，让传统数据信息的管理升级为软件存储，归纳，集中处理数据信息的管理方式。本图书商城管理系统就是在这样的大环境下诞生，其可以帮助管理者在短时间内处理完毕庞大的数据信息，使用这种软件工具可以帮助管理人员提高事务处理效率，达......
  • 【计算机毕业设计】springboot001基于SpringBoot的在线拍卖系统
    随着社会的发展，社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。在线拍卖系统，主要的模块包括管理员；首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单管理、留言板管理、系统管理，用户；首页、个人......
  • 【计算机毕业设计】springboot002基于springboot的医护人员排班系统
    随着信息技术在管理上越来越深入而广泛的应用，管理信息系统的实施在技术上已逐步成熟。本文介绍了医护人员排班系统的开发全过程。通过分析医护人员排班系统管理的不足，创建了一个计算机管理医护人员排班系统的方案。文章介绍了医护人员排班系统的系统分析部分，包括可行性分析......
  • 【计算机毕业设计】springboot003图书个性化推荐系统的设计与实现
    本论文主要论述了如何使用JAVA语言开发一个图书个性化推荐系统，本系统将严格按照软件开发流程进行各个阶段的工作，采用B/S架构，面向对象编程思想进行项目开发。在引言中，作者将论述图书个性化推荐系统的当前背景以及系统开发的目的，后续章节将严格按照软件开发流程，对系统进行各个......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99