递归-5简单的0/1背包问题

//

//ViewController.m

//CocoTest_1

//

//Created by S u p e r m a n on 2017/3/14.

//Copyright © 2017年张浩. All rights reserved.

//

#import"ViewController.h"

staticintmaxM =5;

staticintcount =0;

@interfaceViewController()

@end

@implementationViewController

- (void)viewDidLoad {

[superviewDidLoad];

// Do any additional setup after loading the view, typically from a nib.

intm[10] = {5,2,3,4,9,6,7,8,1,10};

intm_t[10] = {0};

knap(m,0,m_t);

}

/**

设一个背包容纳的物品最大质量为m,现有n件物品，质量为m1,m2,… ,mn,均为正整数。要求从中挑选若干件，使背包质量之和正好为m.

（在此问题中，第i件物品要么取，要么不取，不能取一部分，故问题可能有解，可能无解）

*/

voidknap(int*m,intn,int*m_t) {

if(n <10) {

intsum =0;

for(inti =0; i<10; i++) {

sum += m_t[i];

}

if(sum ==maxM) {

printf("第%02d个: = ",count+1);

for(inti =0; i<10; i++) {

printf(" %d ",m_t[i]);

}

printf("\n");

count++;

}else{

for(inti =0; i<10; i++) {

if(m_t[i] ==0) {//表示当前的是可以插入值

m_t[i] = m[i];//放入一个值

knap(m, n+1,m_t);//放入其余的数

m_t[i] =0;//还原

}

}

}

}

}

@end