#include<stdio.h>
#include<string.h>
#define N 10
int main()
{
  int i,j,n;
  int a[N],dp[N][N];//a[i]表示上端点i对应的下端点坐标，dp数组用来储存上端点到下端点的最大不相交子集
  printf("请输入端点个数：");
  scanf("%d",&n);
  printf("请输入各端点对应的下端点：");
  for(i=1;i<=n;i++){
    scanf("%d",&a[i]);//依次存入上端点对应的下端点 
  } 
  for(i=1;i<=n;i++){//上端点为1的情况 
    if(i<a[1]) dp[1][i]=0;
    else dp[1][i]=1;
  }
  for(i=2;i<=n;i++){//其他情况 
    for(j=1;j<=n;j++){
      if(j<a[i]){//小于対应线的坐标 
        dp[i][j]=dp[i-1][j];
      }else{//大于等于 
        if(dp[i-1][j]>dp[i-1][a[i]-1]+1){//更新dp最大值 
          dp[i][j]=dp[i-1][j];
        }else
          dp[i][j]=dp[i-1][a[i]-1]+1;
      }
    }
  }
  printf("%d\n",dp[n][n]);
  return 0;
 } 

#include <stdio.h>
#include <stdlib.h>
void mnset(int *c, int **size, int n)
{
    int i, j;
    //i=1且j<c[1]时，最大不相交子集为0
    for (j=0;j<c[1];j++)
        size[1][j] = 0;
    // i=1且j>=c[1]时，最大不相交子集为1 
    for(j=c[1];j<=n;j++)
        size[1][j]=1;
    for(i=2;i<n;i++)//一般情况 
    {
        for(j=0;j<c[i];j++)
            size[i][j]=size[i-1][j];//j<c[i]时如果选择该线，则交叉打架，故一律为size数组上方数值 
        for(j=c[i];j<=n;j++)
            size[i][j]=(size[i-1][j]>size[i-1][c[i]-1]+1)?size[i-1][j]:(size[i-1][c[i]-1]+1);
    //前者为不选该线，后者为选用该线 
    }
    size[n][n]=(size[n-1][n]>size[n-1][c[n]-1]+1)?size[n-1][n]:size[n-1][c[n]-1]+1;
}
int traceback(int *c, int **size, int *net, int n)//回溯追踪 
{//net数组存储mnset中的m条连线 
    int i,j,m=0;
    j=n;
    for(i=n;i>1;i--)
    {
        if(size[i][j]!=size[i-1][j])//表示没选择当前线 
        {
            net[m++]=i;
            j=c[i]-1;
        }
    }
    if(j>=c[1])
        net[m++]=1;
    return m;
}
void print(int *c,int **size,int *net,int n,int m)
{
  printf("S[i,j]数组为：\n");
      int i,j;
      for (i=1;i<=n;i++)
      {
      for(j=0;j<=n;j++)
            printf("%d ",size[i][j]);
      printf("\n");
    }
    printf("\n");
//输出上端线路编号
      printf("上端线路编号：");
      for(i=0;i<=n;i++)
          printf("%d ",i);
      printf("\n");
//输出下端线路编号
      printf("下端线路编号：");
      for(i=0;i<=n;i++)
          printf("%d ",c[i]);
    printf("\n");
//输出最大不相交子集的个数
      printf("最大不相交子集的大小为：%d\n", size[n][n]);
//输出最大不相交子集中的各个导线
  printf("\n"); 
      printf("上端线路编号：");
      for(i=m-1;i>=0;i--)
          printf("%d ",net[i]);
      printf("\n");
      printf("下端线路编号：");
      for(i=m-1;i>=0;i--)
        printf("%d ",c[net[i]]);
      printf("\n");
}
int main(){
      int n=10,m;
  int *c=(int*)malloc(sizeof(int)*(n+1));
  c[0]=0;c[1]=8;c[2]=7;c[3]=4;c[4]=2;c[5]=5;c[6]=1;c[7]=9;c[8]=3;c[9]=10;c[10]=6;
      int **size=(int**)malloc(sizeof(int*)*(n+1));
      int *net=(int*)malloc(sizeof(int)*(n+1));
//对c[]进行赋初值
//    c[1] = rand() % n + 1;
//    int i = 2;
//    while (i <= n)
//    {
//        int f = 0;
//        int t = rand() % n + 1;
//        int j=0; 
//        for (j = 1; j < i; j++)
//        {
//            if (c[j] == t)
//            {
//                f = 1;
//                break;
//            }
//        }
//        if (f == 0)
//        {
//            c[i] = t;
//            i++;
//        }
//    }
  int i;
      for(i=1;i<=n;i++)
          size[i]=(int*)malloc(sizeof(int)*(n+1));
      mnset(c,size,n);
    m=traceback(c,size,net,n);
      print(c,size,net,n,m);
      for(i=1;i<=n;i++)
        free(size[i]);
      free(c);
      free(size);
      free(net);
      return 0;
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int max(int x,int y){
  int retValue=x>y?x:y;
  return retValue;
}
void knapsack(int n,int c,int *w,int *v,int **m){
  int i,j;
  //当背包重量为0时，c[i][0]=0; 
  for(i=0;i<=n;i++)
    m[i][0]=0; 
  //边界条件：只有第n个物体，背包容量分别为1,2，…,c的时候m的值
  for(j=1;j<=c;j++)
        if(j>=w[n])
          m[n][j]=v[n];
        else 
      m[n][j]=0;
  //依次求解m[i][j],1<=i<n,1<=j<=c      
  for(i=n-1;i>=1;i--) 
    for(j=1;j<=c;j++)
      if(j<w[i])
        m[i][j]=m[i+1][j];
      else
        m[i][j]=(m[i+1][j]>(m[i+1][j-w[i]]+v[i]))?m[i+1][j]:(m[i+1][j-w[i]]+v[i]);
  printf("最大价值为：%d\n",m[1][c]);
}
//具体选了哪些物品 
void traceback(int **m ,int *w, int c, int n, int *x){//回溯求选用的物品 
  //求x[i]，从m[1][c]开始
  int j=c,i;
  for(i=1;i<n;i++){
      if(m[i][j]==m[i+1][j])//没有物品增加 
          x[i]=0;
      else{
          x[i]=1;
        j=j-w[i];
    }
  }
  if (m[i][j]>0)
      x[n]=1;
  else               
      x[n]=0;
}
int main(){
  int n;//商品总数 
  int c;//背包总容量
  printf("商品总数：");
  scnaf("%d",&n);
  printf("\n"); 
  printf("背包总容量：");
  scanf("%d",&c);
  int *w=(int*)malloc(sizeof(int)*(n+1));//动态分配weights
  int *v=(int*)malloc(sizeof(int)*(c+1));//动态分配values
  int *x=(int*)malloc(sizeof(int)*(n+1));//动态分配所选择的商品 
  int i;
  for(i=1;i<=n;i++)
    scanf("%d",&w[i]);//start with index 1
  for(i=1;i<=n;i++)
    scanf("%d",&v[i]);//start with index 1
  w[0]=0;v[0]=0;
  int **m=(int**)malloc(sizeof(int*)*(n+1));//m[i][j] means j capacity with i...n goods to choose
  for(i=0;i<n+1;i++){
    m[i]=(int*)malloc(sizeof(int)*(c+1));
  }
  knapsack(n,c,w,v,m);
  traceback(m,w,c,n,x);
  printf("goods chosed:");
  for(i=1;i<=n;i++)
    if(x[i]==1)
      printf("%d ",i); 
}

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
void knapsack(int n,int c,int *w,int *v,int **m){
  int i,j;
  //当背包重量为0时，c[i][0]=0; 
  for(i=0;i<=n;i++)
    m[i][0]=0; 
  //边界条件：只有第n个物体，背包容量分别为1,2，…,c的时候m的值
  for(j=1;j<=c;j++)
        if(j>=w[n])
          m[n][j]=v[n];
        else 
      m[n][j]=0;
  //依次求解m[i][j],1<=i<n,1<=j<=c      
  for(i=n-1;i>=1;i--) 
    for(j=1;j<=c;j++)
      if(j<w[i])//剩余容量j小于当前物品重量w[i]，装不下 
        m[i][j]=m[i+1][j];
      else//否则进行价值比较 
        m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
  printf("最大价值为：%d\n",m[1][c]);
}
int max(int x,int y){//这里不使用C自带的三目运算符，使用了就会发生错误(不知道为什么) 
  int bigger=x>y?x:y;
  return bigger;
}
//具体选了哪些物品 
void traceback(int **m ,int *w, int c, int n, int *x){
  //求x[i]，从m[1][c]开始
  int j=c,i;
  for(i=1;i<n;i++){
        if(m[i][j]==m[i+1][j])//没有物品增加 
            x[i]=0;//记x[i]=0
        else{//选择该物品
            x[i]=1;//记x[i]=1
          j=j-w[i];//从背包剩余容量j中减去当前选择物品i的重量w[i]
    }
  }
  if (m[i][j]>0)
      x[n]=1;
  else               
      x[n]=0;
}
int main(){
  int n;//nums of goods 
  printf("物品数量：");
  scanf("%d",&n);
  int c;//capacity
  printf("背包容量：");
  scanf("%d",&c);
  int *w=(int*)malloc(sizeof(int)*(n+1));//weights
  int *v=(int*)malloc(sizeof(int)*(c+1));//values
  int *x=(int*)malloc(sizeof(int)*(n+1));//goods chosed
  int i;
  printf("依次输入物品重量："); 
  for(i=1;i<=n;i++)
    scanf("%d",&w[i]);//start with index 1
  printf("依次输入物品价值："); 
  for(i=1;i<=n;i++)
    scanf("%d",&v[i]);//start with index 1
  w[0]=0;v[0]=0;//0号商品的重量和价值都为0，作为边界条件 
  int **m=(int**)malloc(sizeof(int*)*(n+1));//m[i][j]意味着剩余容量j，当前选择待物品为i...n
  for(i=0;i<n+1;i++){
    m[i]=(int*)malloc(sizeof(int)*(c+1));
  }
  knapsack(n,c,w,v,m);
  traceback(m,w,c,n,x);
  printf("选择物品:");
  for(i=1;i<=n;i++)
    if(x[i]==1)
      printf("%d ",i); 
}

#include <stdio.h>
int max(int a,int b){
  return a>b?a:b;
}
void MNS(int a[],int set[][11],int n){
    int i,j;
    for (i = 0; i < n; i++){      //保证不会将 a 数组中的第一个元素纳入到最长公共子序列中
        set[i][0] = 0;
        set[0][i] = 0;
    }
    for (i = 1; i <= n; i++){
        for (j = 1; j <= n; j++){
            if (a[i] != j)
                set[i][j] = max(set[i-1][j],set[i][j-1]);
            else
                set[i][j] = set[i-1][j-1] + 1;
        }
    }
}
void Traceback(int i,int j,int set[][11]){
    if (i == 0)
        return;
    if (set[i][j] == set[i-1][j])
        Traceback(i-1,j,set);
    else if (set[i][j] == set[i][j-1])
        Traceback(i,j-1,set);
    else{
        Traceback(i-1,j-1,set);
        printf("(%d,%d) ",i,j);
    }
}
int main(){
    int a[] = {0,8,7,4,2,5,1,9,3,10,6};
    int set[11][11];
    MNS(a,set,10);
    printf("最大连线数量为: %d \n",set[10][10]);
    printf("所选连线如下:");
    Traceback(10,10,set);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
int m[10][10];
int x[10];
void Traceback(int [],int ,int );
void knapsack(int [],int [],int ,int );
void knapsack(int v[],int w[],int c,int n){
  int i,j,jMax;
  jMax=w[n]-1<c?w[n]-1:c;
  for(j=0;j<=jMax;j++)
    m[n][j]=0;
  for(j=w[n];j<=c;j++)
    m[n][j]=v[n];
  for(i=n-1;i>1;i--){
    jMax=(w[i]-1)<c?(w[i]-1):c;
    for(j=0;j<=jMax;j++)
      m[i][j]=m[i+1][j];
    for(j=w[i];j<=c;j++)
      m[i][j]=m[i+1][j]>(m[i+1][j-w[i]]+v[i])?m[i+1][j]:(m[i+1][j-w[i]]+v[i]);
  }
  m[1][c]=m[2][c];
  if(c>=w[1])
    m[1][c]=m[1][c]>(m[2][c-w[1]]+v[1])?m[1][c]:(m[2][c-w[1]]+v[1]);
}
void Traceback(int w[],int c,int n){
  int i;
  for(i=1;i<n;i++){
    if(m[i][c]==m[i+1][c])
      x[i]=0;
    else{
      x[i]=1;
      c-=w[i];
    }
  }
  x[n]=m[n][c]?1:0;
  printf("向量x的值依次是:");
  for(i=1;i<=n;i++)
    printf("%d ",x[i]);
}
int main(){
  int n=5,C=10;
  int w[]={0,2,2,6,5,4};
  int v[]={0,6,3,5,4,6};
  knapsack(v,w,C,n);
  printf("此背包问题的最优值是%d\n",m[1][C]);
  Traceback(w,C,n);
  return 0;
}

//长江游艇问题
//租用游艇问题
//长江游艇俱乐部在长江上设置了n个游艇出租站1，2，...，n。 
//游客可在这些游艇出租站租用游艇，并在下游任何一个游艇出租站归还游艇。
//游艇出租站i到游艇出租站j之间的租金为r(i,j)。试设计一个算法，计算出游艇出租站1到游艇出租站n所需的最少租金
#include<stdio.h>
#define n 6
//static int choice[n][n]={0};
void MinCost(int fee[n][n], int dist[n][n]){
      int i,j,k;
//    int choose[n][n]={0};
      for(i=0; i<n; i++)
        for(j=0; j<n; j++)
              dist[i][j] = fee[i][j];//初始化数组 
      for(k=0; k<n; k++)//暴力算法 
        for(i=0; i<n; i++)
              for(j=0; j<n; j++)
                    if(dist[i][k]+dist[k][j] < dist[i][j])//{//如果找到i到j的最省路径：i到k再由k到j 
                        dist[i][j] = dist[i][k]+dist[k][j];//则更行最省路径
//          choose[i][j]=1;//choice数组置1，表示选择该数组
//        }
//  return choose;
}
int main()
{
  int i=0,j=0;
      int fee[n][n]= {
      {0,9,14,18,25,40},
      {3,0,6, 15,18,30},
      {15,7,0,10,12,15},
      {18,17,10,0,4,7},
      {29,18,10,4,0,3},
      {34,23,15,7,4,0}
      };
      printf("各出租站之间的到达租金为：\n");
      for(i=0;i<n;i++)
    for(j=0;j<n;j++){
          printf("%3d ",fee[i][j]);
          if(j==n-1)
            printf("\n");
    }
  printf("\n");
//  int **a;
  int minCost[n][n];//构造存放最小租金的二维数组 
//  a=Mincost(fee, minCost,choice);
//  static int choice[n][n]={0};
//  for(i=0;i<n;i++)
//    for(j=0;j<n;j++)
//      printf("%d",a[i][j]); 
      MinCost(fee, minCost); 
      printf("从出租站1到出租站%d的最少花费为：%d元\n", n-1,minCost[0][5]);
      return 0;
}

#include <stdio.h>
int dis[205][205]; // dis[i][j]: 从第i站到j站所需的租金
int main(){
  int n, temp;
  printf("请输入出租站的个数:");
  scanf("%d", &n);
  // 输入数据并保存
  printf("请依次给定租金:");
  for(int i = 1; i < n; i++){
      for(int j = i+1; j <= n; j++){
          scanf("%d", &temp);
          dis[i][j] = temp;
      }
  }
  // 计算出站1到站n所需的最少租金
  for(int j = 2; j <= n; j++){ // 1站到j站最少租金
      for(int i = 2; i < j; i++){ // i表示第几行开始
          if(dis[1][j] > dis[1][i] + dis[i][j])
              dis[1][j] = dis[1][i] + dis[i][j];
      }
  } 
printf("%d\n", dis[1][n]);
return 0;
}

#include<iostream>
using namespace std;
int Partition(int a[], int p, int r) {
//分区函数，将数组a在区间[p,r]内的元素按照标记x分为左右两部分
    //定义两个下标i和j，分别指向分区的开头和结尾后面的一格 
    int i=p,j=r+1;
    int x=a[p];    //选择区间第一个元素作为基准值
    int t;
    //当i和j没有相遇时循环
    while(1){
        //从左向右找到第一个大于等于x的元素
        while((a[++i])<x&&i<r);
        //从右向左找到第一个小于等于x的元素
        while(a[--j]>x);
        //注意这俩while只移动i和j，不做其他操作，所以没有循环体 
        //如果i>=j则说明已经扫描完了整个区间，跳出循环
        if (i>=j){
            break;
        }
        //交换a[i]和a[j]，使得小于x的元素都在左侧，大于x的元素都在右侧
        t=a[i];
        a[i]=a[j];
        a[j]=t;
        //此时一次循环完成， 
    }
    //将枢轴x放到分区位置j上
    a[p]=a[j];
    a[j]=x;
    return j;
}
void QuickSort(int a[], int p, int r) {
//快速排序函数，递归实现
    int q;
    //如果区间长度为1或0，则已经有序，直接返回
    if (p<r) {
        //使用Partition函数将数组分为左右两部分
        q=Partition(a,p,r);
        //对左半部分[p,q-1]进行排序
        QuickSort(a,p,q-1);
        //对右半部分[q+1,r]进行排序
        QuickSort(a,q+1,r);
    }
}
double greedy(int x[],int n){
//贪心算法，以等待时间较短者优先
//输出最小平均等待时间 
  QuickSort(x,0,n-1);
  int i;
  for(i=1;i<n;i++)  //计算每个顾客的等待时间，新的x数组为{1,1+12,1+12+33...} 
    x[i]+=x[i-1];
  double t=0;
  for(i=0;i<n;i++)
    t+=x[i];
  t/=n;       //计算最小平均等待时间 
  return t;
}
int main(){
    int t[]={56,12,1,99,1000,234,33,55,99,812};   //10名顾客的等待时间 
    int n=sizeof(t)/sizeof(t[0]);
  printf("平均等待时间为%f",greedy(t,n));
    return 0;
}

#include<iostream>
#include<string.h>
using namespace std;
void delek(char a[], int k){
    int m=strlen(a);
    int i,j;
    if(k>=m){
        a[0]='\0';
        return;
    }
    while(k>0){
        int i;
        for(i=0;i<strlen(a)-1 && (a[i]<=a[i+1]);i++);
        //找到第一个i，使得a[i]>a[i+1]
        for(j=i;j<strlen(a)-1;j++){
        //把这个i删掉（即从i到最后往前挪一位） 
            a[j]=a[j+1];
        }
        a[strlen(a)-1]='\0'; //将字符串最后一位设为'\0'，以便输出结果 
        k--;
    }
    while(strlen(a)>1 && a[0]=='0'){
    //删除前导零
        for(int j=0;j<strlen(a)-1;j++){
            a[j]= a[j+1];
        }
        a[strlen(a)-1]='\0'; //将字符串最后一位设为'\0'，以便输出结果 
    }
}
int main(){
    char a[]="178543";     //以字符串的形式给定原数字 
    printf("删数前的数字为：%s\n",a);
    printf("输入要删掉的位数:");
    int k=0;
    scanf("%d",&k);
//  int k=4;         //要删掉几位 
//  printf("Before: %s\n", a);
    delek(a,k);
    printf("删掉%d位后的数字为: %s\n",k,a);
    return 0;
}

#include<stdio.h>
#include<stdlib.h>
void GreedySelector(int n,int s[],int f[],bool A[]){//活动结束时间按非减排序 
//共有n个活动，s[i]为第1个活动开始时间，f[i]为第i个活动结束时间，A[]用于记录是否选择该活动 
  A[1]=true;//选择第1个活动，每次选择最早结束的活动 
  int i,j=1;
  for(i=2;i<=n;i++){
    if(s[i]>=f[j]){//若活动i开始时间s[i]晚于活动j结束时间f[j] 
      A[i]=true;//选择活动A[i] 
      j=i;//并将j置为i 
    }
  else
    A[i]=false;//表示不选择活动A[i]，继续寻找无时间冲突的活动 
  } 
}
int main(){
  int n=11,k=0;
  int s[11]={1,3,0,5,3,5,6,8,8,2,12};
  int f[11]={4,5,6,7,8,9,10,11,12,13,14};
  bool A[11]={};
  for(k=0;k<11;k++){
    printf("活动%d的开始时间为%d，结束时间为%d\n",k+1,s[k],f[k]);   
  }
  GreedySelector(11,s,f,A);
  printf("\n贪心算法选择的活动为：");
  for(k=0;k<11;k++)
    if(A[k]!=0)
      printf("%d ",k);
}

#include<stdio.h>
#include<stdlib.h>
void Knapsack(int n,float M,float v[],float w[],float x[]){//贪心算法解决背包问题(非0-1背包) 
//  Sort(n,v,w);//Sort函数，排序各个物体的单位体积下的价值(价值v/质量w) 
  int i;
  for(i=1;i<=n;i++)//n为所有物品的总大小，用x[i]=0表示没被装入背包，x[i]=1表示被装入背包了 
    x[i]=0;
  float c=M;//c被赋初值为原始背包大小 
  for(i=1;i<=n;i++){
    if(w[i]>c)//背包满了 
      break;
    x[i]=1;//表示这个单位体积的物品被全部装入背包 
    c-=w[i];//现在背包的大小c要被减去装入物品占据的大小 
  }
  if(i<=n)
    x[i]=c/w[i];//x[i]表示第i个物品的所占体积在当前规定背包最大容量M的条件下被装入的比例
        //比如x[i]=0.5，表示第i个物品的一半被放入背包，另一半没有放入 
}
int main(int argc,char *argv[]){
  int n=3,i;
  float M=50;
  float v[]={0,60,100,120};
  float w[]={0,10,20,30};
  float x[3]={0};//x[i]用于存放装入背包的单件物品的多少 
  Knapsack(n,M,v,w,x);
  printf("装入背包的物品为：");
  for(i=1;i<=n;i++)
    printf("%f  ",x[i]);
  return 0; 
}

#include<stdio.h>
#include<stdlib.h>
//应使用短作业优先(需要服务时间短的顾客先服务)的方法
double greedy(int x[]){
  int n=x.size();
  sort(x.begin(),x.end());
  for(int i-1;i<n;i++)
    x[i]+=x[i-1];
  double t=0;
  for(i=0;i<n;i++)
    t+=x[i];
  t/=n;
  return t;
} 
int main(){
  int x[]={56,12,1,99,1000,234,33,55,99,812};
  printf("平均最短服务时间为%d",greedy(x));
}

#include<stdio.h>
#include<stdlib.h>
//n皇后问题 
int n;
int x[20];
int place(int k){
  int i;
  for(i=1;i<k;i++)
    if(abs(k-i)==abs(x[k]-x[i]) || x[k]==x[i])
      return 0;
  return 1;
} 
int queen(){
  int i;
  x[1]=0;
  int t=1;
  int sum=0;
  while(t>0)
  {
    x[t]+=1;
    while(x[t]<=n && !place(t))
      x[t]++;
    if(x[t]<=n)
      if(t==n){
        sum++;
        for(i=1;i<=n;i++) printf("%d ",x[i]);
        printf("\n");
      }
      else
        x[++t]=0;
      else
        t--;
  }
  return sum;
}
int main(int argc,char *argv[]){
  int t;
  printf("请输入要放置的皇后的个数:");
  scanf("%d",&n);
  t=queen();
  printf("共有%d个解\n",t);
  return 0;
}

#include<stdio.h>
#include<stdlib.h>
int n;//物品数量
double c;//背包容量
double v[100];//各个物品的价值 value
double w[100];//各个物品的重量 weight
double cw=0.0;//当前背包重量 current weight
double cp=0.0;//当前背包中物品总价值 current price
double bestp=0.0;//当前最优价值 best price
double perp[100];//单位物品价值(排序后) per price
int order[100];//物品编号
int put[100];//设置是否装入，为1的时候表示选择该组数据装入，为0的时候表示不装入
//按单位价值排序
void knapsack(){
  int i,j;
  int temporder=0;
  double temp=0.0;
  for(i=1;i<=n;i++)
    perp[i]=v[i]/w[i];//计算单位价值(单位重量的物品价值) 
  for(i=1;i<=n-1;i++)
  {
    for(j=i+1;j<=n;j++)
      if(perp[i]<perp[j])//冒泡排序prep[],order[],sortv[],sortw[]
      {
        temp=perp[i];//冒泡对prep[]排序
        perp[i]=perp[i]; 
        perp[j]=temp;
        temporder=order[i];//冒泡对order[]排序
        order[i]=order[j]; 
        order[j]=temporder;
        temp=v[i];//冒泡对v[]排序
        v[i]=v[j];
        v[j]=temp;
        temp=w[i];//冒泡对w[]排序
        w[i]=w[j];
        w[j]=temp; 
      }
  }
} 
//回溯函数
void backtrack(int i){//i用来指示到达的层数(第几步，从0开始)，同时也指示当前选择完了几层
  double bound(int i);
  if(i>n){//递归结束的判定条件 
    bestp=cp;
    return; 
  } 
  //如若左子结点可行，则直接搜素左子树
  //对于右子树，先计算上界函数，以判断是否将其减去
  if(cw+w[i]<=c){//将物品i放入背包，搜索左子树
    cw+=w[i];//同步更新当前背包的重量
    cp+=v[i];//同步更新当前背包的总价值
    put[i]=1;
    backtrack(i+1);//深度搜索进入下一层
    cw-=w[i];//回溯复原 
    cp-=v[i];//回溯复原 
  }
  if(bound(i+1)>bestp)//如若符合条件则搜索右子树
    backtrack(i+1); 
} 
//计算上界函数，功能为剪枝
double bound(int i){//判断当前背包的总价值cp+剩余容量可容纳的最大价值<=当前最优价值 
  double leftw=c-cw;//剩余背包容量
  double b=cp;//记录当前背包的总价值cp，最后求上界
  //以物品单位重量价值递减次序装入物品
  while(i<=n && w[i]<=leftw){
    leftw-=w[i];
    b+=v[i];
    i++;
  } 
  //装满背包
  if(i<=n)
    b+=v[i]/w[i]*leftw;
  return b;//返回计算出的上界 
} 
int main(int argc,char *argv[]){
  int i;
  printf("请输入物品的数量和背包的容量：");
  scanf("%d %lf",&n,&c);
  printf("请依次输入%d个物品的重量：\n",n);
  for(i=1;i<=n;i++){
    scanf("%lf",&w[i]);
    order[i]=i;
  }
  printf("请依次输入%d个物品的价值：\n",n);
  for(i=1;i<=n;i++){
    scanf("%lf",&v[i]);
  }
  knapsack();
  backtrack(1);
  printf("最优价值为：%lf\n",bestp);
  printf("需要装入的物品编号是：");
  for(i=1;i<n;i++){
    if(put[i]==1)
      printf("%d ",order[i]);
  }
  return 0;
} 

//装载问题
#include<stdio.h>
#include<stdlib.h>
int n;//集装箱数
int cw;//当前载重量，current weight
int bestw;//最优载重重量
int r;//剩余集装箱重量
int c1;//第一艘轮船的载重量
int c2;//第二艘轮船的载重量
int x[100];//当前解
int bestx[100];//当前最优解
int w[100];//集装箱重量数组
void BackTrack(int i)
{
  if(i>n)
  {
    if(cw>bestw)
    {
      for(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];
} 
int main(int argc,char *argv[]){
  int i;
  int restweight=0;
  printf("请输入货物的个数n:");
  scanf("%d",&n);
  printf("请分别输入两艘轮船的载重量c1和c2:");
  scanf("%d %d",&c1,&c2);
  printf("请依次输入每件货物的重量:");
  for(i=1;i<=n;i++)
    scanf("%d",&w[i]);
  bestw=0;
  r=0;
  cw=0;
  for(i=1;i<=n;i++)
    r+=w[i];
  BackTrack(1);
  for(i=1;i<=n;i++)
    if(bestx[i]==0)
      restweight+=w[i];
  if(restweight>c2)
    printf("不能装入\n");
  else
  {
    printf("船1装入的货物为:");
    for(i=1;i<=n;i++)
      if(bestx[i]==1)
        printf(" %d",i);
    printf("\n船2装入的货物为:");
    for(i=1;i<=n;i++)
      if(bestx[i]!=1)
        printf(" %d",i);
  }
  return 0;
} 

#include<stdio.h>
#define maxl 1000    //表示最大连续值 
#define maxint 32767
int n,m;            //n为邮票种类数，m为能贴的最大张数 
int maxvalue;       //表示最大连续值
int bestx[100];     //表示最优解
int y[maxl];        //y[k]，存储表示到k值，所使用的最少邮票数 
int x[100];         //存储当前解 
void backtrace(int i,int r);
int main(){
  printf("请输入邮票面值数：");
  scanf("%d",&n);
  printf("请输入能张贴邮票的最大张数：");
  scanf("%d",&m);
  for(int i=0;i<=n;i++){
      x[i]=0;
      bestx[i]=0;
  } 
  for(int i=0;i<maxl;i++){
      y[i]=maxint;
  }
  x[1]=1;
  y[0]=0;
  maxvalue=0;
  backtrace(1,0);
  printf("当前最优解为：");
  for(int i=1;i<=n;i++){
      printf("%d ",bestx[i]);
  } 
  printf("\n最大连续邮资为：");
  printf("%d",maxvalue);
  return 1;
} 
void backtrace(int i,int r){
  for(int j=0;j<=x[i-1]*m;j++){        //对上一层的邮资值数组进行更新，上限是x[i-1]*m 
    if(y[j]<m){
      for(int k=1;k<=m-y[j];k++){      //从只使用一个x[i]到使用m-y[i]个，即使用最多的最大值，降低邮票数 
          if(y[j]+k<y[j+x[i]*k]){
            y[j+x[i]*k]=y[j]+k;   
//如果前面的某一个情况加上k个x[i]，所达到邮资值使用的邮票数少于原来的邮票数则更新 
            }
        }
      }
  }
  while(y[r]<maxint){                    //向后寻找最大邮资值 
      r++;
  }
  if(i==n){                              //i=n表示到达叶子节点。 
      if(r-1>maxvalue){                //若大于最大值，则更新最优值与最优解 
        for(int k=1;k<=n;k++){
                bestx[k]=x[k];    
        }
        maxvalue = r-1;
      }
    return;
  }
  int z[maxl];
  for(int k=0;k<maxl;k++){               //由于每一层需要对多种情况进行运算，因此需要将上一层的邮资值数组保留 
      z[k] = y[k];
  }
  for(int j=x[i]+1;j<=r;j++){            //对下一层进行运算 
      x[i+1]=j;
      backtrace(i+1,r-1);
      for(int k=0;k<maxl;k++)
        y[k]=z[k];
    }
}