//
//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
