//
//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,0);
}
/**
設(shè)一個(gè)背包容納的物品最大質(zhì)量為m,現(xiàn)有n件物品鹰贵，質(zhì)量為m1,m2,… ,mn,均為正整數(shù)诈豌。要求從中挑選若干件，使背包質(zhì)量之和正好為m.
（在此問(wèn)題中，第i件物品要么取，要么不取，不能取一部分，故問(wèn)題可能有解俯艰，可能無(wú)解）
*/
voidknap(int*m,intn,int*m_t,intstartIndex) {
if(n <10) {
intsum =0;
for(inti =0; i<10; i++) {
sum += m_t[i];
}
if(sum ==maxM) {
printf("第%02d個(gè): = ",count+1);
for(inti =0; i<10; i++) {
printf(" %d ",m_t[i]);
}
printf("\n");
count++;
}else{
for(inti = startIndex; i<10; i++) {
if(m_t[i] ==0) {//表示當(dāng)前的是可以插入值
m_t[i] = m[i];//放入一個(gè)值
knap(m, n+1,m_t,i+1);//放入其余的數(shù)
m_t[i] =0;//還原
}
}
}
}
}
@end
