/*設(shè)有一個背包可以放入物品的重量為s，現(xiàn)有n件物品，重量分別為w[0],w[1],……,w[n-1]。
問題是能否從這n件物品中選擇若干件放入此背包中使得放入的重量之和正好等于s。
如果存在一種符合上述要求的選擇，則稱此問題有解；
否則稱此問題無解。試用分而治之的算法設(shè)計方法設(shè)計求解背包問題的函數(shù)。*/

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define sl system("cls")		//定義系統(tǒng)清屏函數(shù)的宏
#define ff fflush(stdin)		//定義清除緩存函數(shù)的宏
   using namespace std;
void menu1()						//程序開始時輸出的用戶界面
{
	char s;		
		cout<<"\t\t*------------------------------------------------*\n";
	cout<<"\t\t*                                                *\n";
    cout<<"\t\t*     ^V^ 歡迎使用 ***解決背包問題程序*** ^V^      *\n";
	cout<<"\t\t*	         方法：分而治之                      *\n";
	cout<<"\t\t*             制作人：王萬祿                     *\n";
	cout<<"\t\t*                                                   *\n";
   	cout<<"\t\t*------------------------------------------------*\n";
	cout<<"\t\t*                  用戶登錄                      *\n";

    cout<<"請按任意字母鍵繼續(xù) "<<endl;
	cin>>s;
//ff;
//sl;
}
 int w[100];  //:存放n件物品的重量
 int s=-1,n=-1;    // s:背包中所能承受的物品總重量 n:物品的數(shù)量
void input()
{  //用戶輸入問題的相關(guān)數(shù)據(jù)并對數(shù)據(jù)排序
    int i,j,t;//i，j,k,t：臨時變量
    cout<<"The number of object:" ;
	while(n<0)
	{
	  cin>>n;
	if(n<0)cout<<"物品件數(shù)不能為負數(shù)或0請輸入正確的數(shù)據(jù)，謝謝合作！"<<endl;
//	cin>>n;
	}
	//ff;
	//sl;
    cout<<"Total weight=";  
	while(s<0)
	{
	cin>>s;
	if(s<0)cout<<"背包重量不能為小于零，請重新輸入！"<<endl;
	}
   // ff;
    cout<<"Weight of each object:";
    for(i=0;i<n;i++)
        cin>>w[i];
	//用選擇法排序?qū)⑦@些數(shù)從大到小排序
	for(i=0;i<n;i++)
      for(j=i+1;j<n;j++)
     if(w[i]<w[j])
		{
		t=w[i];w[i]=w[j];w[j]=t;
		}
	cout<<"背包的重量降序排列后為："<<endl;
    for(i=0;i<n;i++)
        cout<<w[i]<<endl;
	cout<<"總共有"<<n<<"件物品"<<endl;
}
int flag=0;
void beibao(int s,int *a,int n)//s為剩余重量，a為物體重量,n件物品
	{
	if(s==0) {flag=1;return;}
	else
		if(s<0) 1;
		else 
			if(s>0&&n<1)1;
		    else
			{
              beibao(s,a,n-1);
			  beibao(s-a[n-1],a,n-1);
			} 
	}
void main()
{
 menu1(); 
 input();
 beibao(s,w,n);
	 if(flag==1)cout<<"此題有解！"<<endl;
 else cout<<"此題無解！"<<endl;
}