算法的一些小心得

1、插入排序

简单插入

#include<stdio.h>
void insort(int a[],int n)
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        j=i-1;
        a[0]=a[i];
        while(a[0]<a[j])
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=a[0];
    }
}
void main()
{
    int a[11];
    int i;
    for(i=1;i<=10;i++)
        scanf("%d",&a[i]);
    insort(a,10);
    for(i=1;i<=10;i++)
        printf("%d ",a[i]);
}

 

(1) 选择排序代码：
void sort(int list[], int arraySize) 
{ 
 for (int i = arraySize - 1; i >= 1; i--) 
 { 
 //2 分：定义变量
 int currentMin = list[0]; 
 int currentMinIndex = 0; 
 //4 分：寻找最小值并记录位置
 for (int j = 1; j <= i; j++) 
 { 
 if (currentMin > list[j]) 
 { 
 currentMin = list[j];
 currentMinIndex = j; 
 } 
 } 
 //4 分：交换 list[i]和 list[currentMinIndex] 
 if(currentMinIndex != i) 
 { 
 list[currentMinIndex] = list[i]; 
 list[i] = currentMin; 
 } 
 } 
 //2 分：输出结果
 for(int m = 0; m < arraySize; m++) 
 { 
 cout << list[m] << " "; 
 } 
} 
(2) 插入排序代码：
void sort(int list[], int arraySize) 
{ 
 for (int i = 1; i < arraySize; i++) 
 { 
 //2 分：将 list[i]插入一个已排序的集合 list[0…i-1]，当前元素为 list[i] 
 int currentElement = list[i]; 
 int k; 
 //6 分：从 i-1 位置开始寻找插入位置，如果发现有元素大于 list[i]，则插在该元素
 //后面，实现由大到小排序；并且该位置之后的元素均往后移动一位
 for (k = i -1; k >=0 && list[k] < currentElement; k--) 
 { 
 list[k+1] = list[k]; 
 } 
 //2 分：将当前元素插入 list[k+1] 
 list[k+1] = currentElement; 
 } 
 //2 分：输出结果
 for(int m = 0; m < arraySize; m++) 
 { 
 cout << list[m] << " "; 
 } 
} 

 

 

希尔排序

//希尔排序
#include<stdio.h>
#include<time.h>
#define SWAP(x,y) ((x)=(x)^(y),(y)=(x)^(y),(x)=(x)^(y))
void shell(int a[],int n)
{
    int d=n,i;
    while(d>1)
    {
        d=(d+1)/2;
        for(i=0;i<n-d;i++)
        {
            if(a[d+i]<a[i])
                SWAP(a[d+i],a[i]);
        }
    }
}

void main()
{
    srand(time(0));
    int i,a[10];
    for(i=0;i<10;i++)
    {
        a[i]=rand()%100;
        printf("%d ",a[i]);
    }
    printf("\n");
    shell(a,10);
    for(i=0;i<10;i++)
    {
        printf("%d ",a[i]);
    }
}

2、快速排序

 

#include<stdio.h>
#include<time.h>
#include <iostream>
#define SWAP(x,y) ((x)=(x)^(y),(y)=(x)^(y),(x)=(x)^(y))
//快速排序
int partions(int a[],int left,int right)
{
	int key=a[left];
	while(left<right)
	{
		while(left<right&&a[left]<key)
			++left;
		while(left<right&&a[right]>key)
			--right;
		SWAP(a[left],a[right]);
	}
	a[left]=key;
	return left;
}
void qsort(int a[],int left,int right)
{
	if(left<right)
	{
		int q=partions(a,left,right);
		qsort(a,left,q-1);
		qsort(a,q+1,right);
	}
}
void main()
{
	clock_t start,finish;
	double durtime;
	start = clock();
	srand(time(0));
	int i,a[10];
	for(i=0;i<10;i++)
	{
		a[i]=rand()%100;
		printf("%d ",a[i]);
	}
	printf("\n");
	qsort(a,0,9);
	for(i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
	finish=clock();
	durtime=(double)(finish-start)/CLOCKS_PER_SEC;
	printf("\n%fseconds",durtime);
	system("pause");
}

 

 

3、归并排序

 

//归并排序
#include<iostream>
#include<stdio.h>
#include<time.h>
void merge(int a[],int left,int mid,int right)
{
	int begin1,begin2,end1,end2,k=0,i;
	begin1=left;
	begin2=mid+1;
	end1=mid;
	end2=right;
	//int *temp=(int *)malloc((right-left+1)*sizeof(int));
	int *temp=new int[right-left+1];
	while((begin1<=end1)&&(begin2<=end2))
	{
		if(a[begin1]<a[begin2])
		{
			temp[k++]=a[begin1++];
		}
		else
		{
			temp[k++]=a[begin2++];
		}
	}
	while(begin1<=end1)
		temp[k++]=a[begin1++];
	while(begin2<=end2)
		temp[k++]=a[begin2++];
	for(i=0;i<right-left+1;i++)
		a[left+i]=temp[i];
	delete [](temp);
}
void mergesort(int a[],int left,int right)
{
	if(left<right)
	{
		int mid=(right+left)/2;
		mergesort(a,left,mid);
		mergesort(a,mid+1,right);
		merge(a,left,mid,right);
	}
}
void main()
{
	srand(time(0));
	int i,a[10];
	for(i=0;i<10;i++)
	{
		a[i]=rand()%100;
		printf("%d ",a[i]);
	}
	printf("\n");
	mergesort(a,0,9);
	for(i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
	system("pause");
}

 

4、堆排序

 

//堆排序
#include<iostream>
#include<stdio.h>
#include<time.h>
#define swap(x,y) ((x)=(x)^(y),(y)=(x)^(y),(x)=(x)^(y))
void HeapAdjust(int array[] , int s , int m)   // 对堆进行调整，使下标从s到m的无序序列成为一个大顶堆
{
	int j , temp = array[s];
	for(j = 2*s; j <= m ; j *= 2)
	{
		if(j < m && array[j] < array[j + 1])   // 如果结点的左孩子小于右孩子增加j的值
			++j;              // 用于记录较大的结点的下标
		if(temp >= array[j])  // 如果父结点大于等于两个孩子,则满足大顶堆的定义，跳出循环
			break;
		array[s] = array[j];    // 否则用较大的结点替换父结点
		s = j;          // 记录下替换父结点的结点下标
	}
	array[s] = temp;        // 把原来的父结点移动到替换父结点的结点位置
}

void HeapSort(int array[] , int len)
{
	int i;
	for(i = len / 2; i >= 0 ; --i)    // 建立大顶堆
		HeapAdjust(array , i , len-1);
	for(i = len - 1 ; i > 0 ; --i)
	{
		swap(array[0] , array[i] );       // 第个元素和最后一个元素进行交换
		HeapAdjust(array , 0 , i-1);      // 建立大顶堆
	}
}
void main()
{
	srand(time(0));
	int i,a[10];
	for(i=0;i<10;i++)
	{
		a[i]=rand()%100;
		printf("%d ",a[i]);
	}
	printf("\n");
	HeapSort(a,10);
	for(i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
	system("pause");
}

 

 

5、0-1背包问题：

 

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这个问题的特点是：每种物品只有一件，可以选择放或者不放。

算法基本思想：

利用动态规划思想 ，子问题为：f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。

其状态转移方程是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} //这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。

解释一下上面的方程：“将前i件物品放入容量为v的背包中”这个子问题，如果只考虑第i件物品放或者不放，那么就可以转化为只涉及前i-1件物品的问题，即1、如果不放第i件物品，则问题转化为“前i-1件物品放入容量为v的背包中”；2、如果放第i件物品，则问题转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”(此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i])。则f[i][v]的值就是1、2中最大的那个值。

（注意：f[i][v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。）

优化空间复杂度：

以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。

上面f[i][v]使用二维数组存储的，可以优化为一维数组f[v]，将主循环改为：

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-c[i]]+w[i]};

即将第二层循环改为从V..0，逆序。

解释一下：

假设最大容量M=10，物品个数N=3，物品大小w{3,4,5}，物品价值p{4,5,6}。

当进行第i次循环时，f[v]中保存的是上次循环产生的结果，即第i-1次循环的结果(i>=1)。所以f[v]=max{f[v],f[v-c[i]]+w[i]}这个式子中，等号右边的f[v]和f[v-c[i]]+w[i]都是前一次循环产生的值。

当i=1时，f[0..10]初始值都为0。所以

f[10]=max{f[10],f[10-c[1]]+w[1]}=max{0,f[7]+4}=max{0,0+4}=4;

f[9]=max{f[9],f[9-c[1]]+w[1]}=max{0,f[6]+4}=max{0,0+4}=4;

......

f[3]=max{f[3],f[3-c[1]]+w[1]}=max{0,f[3]+4}=max{0,0+4}=4;

f[2]=max{f[2],f[2-c[1]]+w[1]}=max{0,f[2-3]+4}=0;//数组越界？

f[1]=0;

f[0]=0;

当i=2时，此时f[0..10]经过上次循环后，都已经被重新赋值，即f[0..2]=0,f[3..10]=4。利用f[v]=max{f[v],f[v-c[i]]+w[i]}这个公式计算i=2时的f[0..10]的值。

当i=3时同理。

具体的值如下表所示：

因此，利用逆序循环就可以保证在计算f[v]时，公式f[v]=max{f[v],f[v-c[i]]+w[i]}中等号右边的f[v]和f[v-c[i]]+w[i]保存的是f[i-1][v]和f[i -1][v-c[i]]的值。

当i=N时，得到的f[V]即为要求的最优值。

初始化的细节问题：

在求最优解的背包问题中，一般有两种不同的问法：1、要求“恰好装满背包”时的最优解；2、求小于等于背包容量的最优解，即不一定恰好装满背包。

这两种问法，在初始化的时候是不同的。

1、要求“恰好装满背包”时的最优解：

在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。如果不能恰好满足背包容量，即不能得到f[V]的最优值，则此时f[V]=-∞，这样就能表示没有找到恰好满足背包容量的最优值。

2、求小于等于背包容量的最优解，即不一定恰好装满背包：

如果并没有要求必须把背包装满，而是只希望价值尽量大，初始化时应该将f[0..V]全部设为0。

总结

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

 

0-1背包问题代码：

代码1

#include <iostream>
#include <vector>
using namespace std;
const int MIN=0x80000000;
const int N=3;   //物品数量
const int V=5;  //背包容量
int f[N+1][V+1];

int Package(int *W,int *C,int N,int V);
void main(int argc,char *argv[])
{
 int W[4]={0,7,5,8};      //物品权重
 int C[4]={0,2,3,4};      //物品大小
 int result=Package(W,C,N,V);
 if(result>0)
 {
  cout<<endl;
  cout<<"the opt value:"<<result<<endl;
  int i=N,j=V;
  while(i)
  {
   if(f[i][j]==(f[i-1][j-C[i]]+W[i]))
   {
    cout<<i<<":"<<"w="<<W[i]<<",c="<<C[i]<<endl;
    j-=C[i];
   }
   i--;
  }
 }
 else
  cout<<"can not find the opt value"<<endl;
 return;
}

int Package(int *W,int *C,int N,int V)
{
 int i,j;
 memset(f,0,sizeof(f));  //初始化为0

 for(i=0;i<=N;i++)
 for(j=1;j<=V;j++)               //此步骤是解决是否恰好满足背包容量，
  f[i][j]=MIN;                //若“恰好”满足背包容量，即正好装满背包，则加上此步骤，若不需要“恰好”，则初始化为0
    
 for(i=1;i<=N;i++)
  for(j=C[i];j<=V;j++)
  {
   f[i][j]=(f[i-1][j]>f[i-1][j-C[i]]+W[i])?f[i-1][j]:(f[i-1][j-C[i]]+W[i]);
   cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<endl;
  }
 return f[N][V];
}

其他策略方法见http://zhidao.baidu.com/question/439908883.html

 

6、哈希查找

 

根据关键字的结构和分布的不同，可构造出许多不同的哈希函数，这里主要介绍两种常用的整数类型关键字的哈希函数构造方法。

1）直接定址法

H(Key) = key 或H(key) = a x key + b;

 

2）除留余数法

H(key) = key MOD p ——(p <= m)

 

hash冲突的处理方法

处理哈希冲突的方法可分为开放定址法和链地址法两大类：

1）开放定制法：

就是当冲突发生时，使用某种探测方法在哈希表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个空的地址单元为止，

在开放定制法中，哈希表中的空闲单元（假设其下表为d）不仅允许哈希地址为d的同义词关键字使用，而且也允许发生冲突的其他关键字使用，因为这些关键字

的哈希地址不为d，所以称其为非同义词关键字。

Hi=（H（key）+di） MOD m ——i = 1,2，...，k（k<=m-1）

其中H（key）为哈希函数， m为哈希表表长， di为增量序列， 若di=1,2,3,4.。。m-1，则称为线性探测再散列；

若di = 1， -1， 4， -4.。。。。。则称其为二次探测再散列。

 

2）链地址法：

把所有的同义词链接在同一个单链表中，在这种方法中，哈希表每个单元中存在的不再是对象，而是相应同义词单链表的头指针。

#include <stdio.h>  
#include <stdlib.h>  
  
  
#define Hashmax 11  
#define MAX 20   
  
  
typedef int ElemType;  
  
  
typedef struct HashNode  
{  
ElemType elem;  
struct HashNode *next;  
}HashNode;  
  
  
typedef struct  
{  
HashNode ChainHash[MAX];  
int  count;  
}HashTable;  
  
  
int hash_mod(ElemType key)  
{  
return key % Hashmax;  
}  
  
  
void InsertHash(HashTable *h, int key)  
{  
HashNode *p;  
int index;  
p = (HashNode*)malloc(sizeof(HashNode));  
p->elem = key;  
index = hash_mod(key);  
p->next = h->ChainHash[index].next;  
h->ChainHash[index].next = p;  
h->count++;  
}  
  
  
void CreateHashTable(HashTable *h, int n)  
{  
int key;  
int i;  
for(i = 0; i < n; i++)  
{  
printf("Input the  %d key :", i+1);  
scanf("%d", &key);  
InsertHash(h, key);  
}  
}  
  
  
void PrintHashTable(HashTable *h)  
{  
int i;  
HashNode *p;  
for(i = 0;i <= Hashmax; i++)  
{  
p = h->ChainHash[i].next;  
while(p)  
{  
printf("%-5d", p->elem);  
p = p->next;  
}  
}  
}  
  
  
int SearchHash(HashTable *h, int key)  
{  
HashNode *p;  
int index;  
int counter = 0;  
index = hash_mod(key);  
p = h->ChainHash[index].next;  
while(p)  
{  
if(p->elem == key)  
return 1;  
else   
p = p->next;  
}  
return 0;  
}  
  
void main()  
{  
int n ,key;  
int i;  
HashTable H;  
printf("input the length of the Hash that we want to build:");  
scanf("%d", &n);  
for(i = 0;i <= Hashmax; i++)  
H.ChainHash[i].next = NULL;  
H.count = 0;  
CreateHashTable(&H,n);  
  
  
printf("The hash table that we build is:");  
PrintHashTable(&H);  
  
  
printf("\nInput the key that we want to search(-1 for exit):");  
scanf("%d", &key);  
while(key != -1)  
{  
if(SearchHash(&H, key))  
printf("There is a %d record in the Hash Table!\n", key);  
else  
printf("There is not a %d record in the Hash Table!\n", key);  
  
  
printf("\nInput the key that we want to search(-1 for exit):");  
scanf("%d", &key);  
}  
}  

 

7、二分查找

 

#include<stdio.h>
int Search(int *a,int key)
{               //在顺序表中折半查找key的数据元素。若找到，则函数值为
    int low=0,mid;                //该元素的数组下标；否则为0。
    int high=6;
    while(low <=high)
    {
        mid=(low+high)/2;
        if(key==a[mid])
        {
            return mid;      //找到待查元素
        }
        else if(key <a[mid]) high=mid-1; //继续在前半区间进行查找
        else low=mid+1;            //继续在后半区间进行查找
  }
    return 0;                                      //顺序表中不存在待查元素
}
void main()
{
    int key;
    scanf("%d",&key);
    int a[]={22,33,44,55,66,77,88};
    Search(a,key);
    if(!Search(a,key))
        printf("你要查找的数不在目标数组中！\n");
    else
        printf("你要查找的数的数组下标为 %d \n",Search(a,key));
}

8、递归hanoi

 

 

#include<stdio.h>
int count=0;
void move(char a,char c)
{
    count++;
    printf("%c-->%c  %d\n",a,c,count);
}


void hanoi(int n,char a,char b,char c)
{
    if(1==n)
        move(a,c);
    else
    {
        hanoi(n-1,'a','c','b');
        move(a,c);
        hanoi(n-1,'b','a','c');
    }
}


void main()
{
    int n;
    scanf("%d",&n);
    hanoi(n,'a','b','c');
}

 

9、实现一个队链表排序的算法，C/C++可以使用std::list<int>，Java使用LinkedList<Integer>
要求先描述算法，然后再实现，算法效率尽可能高效。
主要考察链表的归并排序。
要点：需要使用快、慢指针的方法，找到链表的的中间节点，然后进行二路归并排序

 

typedef struct LNode
{
int data;
struct LNode *next;
}LNode , *LinkList;


// 对两个有序的链表进行递归的归并
LinkList MergeList_recursive(LinkList head1 , LinkList head2)
{
LinkList result;
if(head1 == NULL)
return head2;
if(head2 == NULL)
return head1;
if(head1->data < head2->data)
{
result = head1;
result->next = MergeList_recursive(head1->next , head2);
}
else
{
result = head2;
result->next = MergeList_recursive(head1 , head2->next);
}
return result;
}


// 对两个有序的链表进行非递归的归并
LinkList MergeList(LinkList head1 , LinkList head2)
{
LinkList head , result = NULL;
if(head1 == NULL)
return head2;
if(head2 == NULL)
return head1;
while(head1 && head2)
{
if(head1->data < head2->data)
{
if(result == NULL)
{
head = result = head1;
head1 = head1->next;
}
else
{
result->next = head1;
result = head1;
head1 = head1->next;
}
}
else
{
if(result == NULL)
{
head = result = head2;
head2 = head2->next;
}
else
{
result->next = head2;
result = head2;
head2 = head2->next;
}
}
}
if(head1)
result->next = head1;
if(head2)
result->next = head2;
return head;
}


// 归并排序，参数为要排序的链表的头结点，函数返回值为排序后的链表的头结点
LinkList MergeSort(LinkList head)
{
if(head == NULL)
return NULL;
LinkList r_head , slow , fast;
r_head = slow = fast = head;


// 找链表中间节点的两种方法
/*
while(fast->next != NULL)
{
if(fast->next->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
else
fast = fast->next;
}*/


while(fast->next != NULL && fast->next->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}

if(slow->next == NULL)    // 链表中只有一个节点
return r_head;
fast = slow->next;
slow->next = NULL;
slow = head;
// 函数MergeList是对两个有序链表进行归并，返回值是归并后的链表的头结点
//r_head = MergeList_recursive(MergeSort(slow) , MergeSort(fast));
r_head = MergeList(MergeSort(slow) , MergeSort(fast));
return r_head;
}

 

10、约瑟夫环问题

 

#include <iostream>
using namespace std;
typedef struct Jos
{
	struct Jos *next;
	int data;
}Jos;


void main()
{
	cout<<"输入总人数和间隔\n";
	int M,N,n=0;
	cin>>N>>M;
	Jos *p,*r;
	p=(Jos*)malloc(sizeof(Jos)*(N+1));
	r=p;
	for (int i=1;i<=N;i++)
	{
		r->data=i;
		r->next=p+i;
		r=r->next;
	}
	r->data=N;
	r->next=p;//采用循环单链表实现
	while(r!=r->next)
	{
		for (int i=0;i<M-1;i++)
		{
			r=r->next;
		}
		++n;
		if(n%10==0)
			cout<<endl;
		cout<<r->next->data<<"   ";
		r->next=r->next->next;
	}
	cout<<endl;
	cout<<r->data<<endl;
	free(p);
	system("pause");
}

 

11、八皇后问题

 

#include <iostream>
using namespace std;
#define N 8
int count=0;
int M[N]={0},L[2*N]={0},R[2*N]={0};
int A[N][N]={0};
void print(int A[N][N])
{
	int i,j;
	for(i=0;i<N;i++)
	{
		for (j=0;j<N;j++)
			cout<<" "<<A[i][j];
		cout<<endl;
	}
}
int mytry(int i,int M[N],int L[2*N],int R[2*N],int A[N][N])//八皇后问题回溯思想
{
	for (int j=0;j<N;j++)
		if (!M[j]&&!L[i-j+N]&&!R[i+j])
		{
			A[i][j]=i+1;
			M[j]=L[i-j+N]=R[i+j]=1;
			if (i==N-1)
			{
				print(A);
				cout<<endl;
				count++;
			}
			else
				mytry(i+1,M,L,R,A);
			A[i][j]=0;
			M[j]=L[i-j+N]=R[i+j]=0;
		}
	return count;
}
void main()
{
	int n=mytry(0,M,L,R,A);
	cout<<"count="<<n<<endl;
	system("pause");
}

12、合唱队形

 

 

#include <iostream>
using namespace std;
#define MAX 10
void main()
{
	int n,a[MAX],b[MAX],c[MAX],i,j,max;
	cin>>n;
	for (i=1;i<=n;i++)
		cin>>a[i];
	memset(b,0,sizeof(a));
	memset(c,0,sizeof(c));
	b[1]=1;
	for (i=2;i<=n;i++)//求左侧最长上升子序
	{
		max=0;
		for (j=i-1;j>=1;j--)
			if(a[j]<a[i]&&b[j]>max)
				max=b[j];
			b[i]=max+1;
	}
	c[n]=1;
	for (i=n-1;i>=0;i--)//求左侧最长上升子序
	{
		max=0;
		for (j=i+1;j<=n;j++)
			if(a[j]<a[i]&&c[j]>max)
				max=c[j];
		c[i]=max+1;
	}
	max=b[1]+c[1];
	for (i=2;i<=n;i++)
	{
		if (b[i]+c[i]>max)
			max=b[i]+c[i];
	}
	cout<<n-max+1<<endl;
	system("pause");
}

13、0-1背包问题

 

 

#include <iostream>
#include <iomanip>
using namespace std;
#define  N 5
int v[]={6,3,6,5,4},w[]={2,2,4,6,5};
int C=10;
int cp;
int bestp=0;
int x[N];
int bestx[N];

void putout()
{
	cout<<"物品放入背包的状态为： ";
	for (int i=0;i<N;i++)
		cout<<setw(5)<<x[i];
	cout<<"  获得的价值="<<cp;
	cout<<endl;
}
void knap(int t)//背包问题回溯算法实现
{
	if (t>=N)
	{
		if (bestp<cp)
		{
			bestp=cp;
			for(int j=0;j<N;j++)
				bestx[j]=x[j];
		}
		putout();
	}
	else
	{
		if (w[t]<=C)
		{
			x[t]=1;
			cp+=v[t];
			C-=w[t];
			knap(t+1);
			x[t]=0;
			C+=w[t];
			cp-=v[t];
			x[t]=0;
		}
		x[t]=0;
		knap(t+1);
	}
}
void main()
{
	knap(0);
	cout<<"最优价值："<<bestp<<"\t";
	cout<<"此时放入背包物品：";
	for (int j=0;j<N;j++)
	{
		if (bestx[j]==1)
		{
			cout<<j+1<<" ";
		}
	}
	cout<<endl;
	system("pause");
}