// 背包問題（非遞歸）.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;
//本程序是用來求多個解的，采用的就是簡單的窮舉方法。
int n=0;
void choose(int a,int *b){    //將a轉換成二進制表示
	for (int i=0;i<=n-1;i++){
		b[i]=a-(a/2)*2;
	    a=(a-b[i])/2;
	}
};
void main(){
	int can_or_not=0;
	double s;
    cout<<"請輸入背包的載重量:"<<endl;
    cin>>s;
	cout<<"請輸入物品的個數:"<<endl;
	cin>>n;
    double W[100][2];
    int could_take[100];
    cout<<"請依次輸入各物品的重量："<<endl;
   // cin>>W[0][1];
   // W[0][0]=0;
    for (int i=0;i<=n-1;i++){
	    cin>>W[i][1];
        W[i][0]=0;
	}
    int square=1;
    for (i=1;i<=n;i++) square=square*2;
    
    for (i=0;i<=square-1;i++){
		choose(i,could_take);
        int ans=0;
        for (int j=0;j<=n-1;j++)   ans=ans+W[j][could_take[j]];
        if (ans==s){
			can_or_not=1;
	        cout<<"可以攜帶的物品重量為："<<endl;
	        for (int p=0;p<=n-1;p++)
            if(W[p][could_take[p]]!=0) cout<<W[p][could_take[p]]<<endl;
		};
	}
    if (can_or_not==0) cout<<"沒有符合條件的解!"<<endl;
}