//
//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,現(xiàn)有n件物品肩钠，質量為m1,m2,… ,mn,均為正整數(shù)哨鸭。要求從中挑選若干件家制，使背包質量之和正好為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);//放入其余的數(shù)
m_t[i] =0;//還原
}
}
}
}
}
@end
