背包问题9月5日.cpp

简单的背包问题

/*设有一个背包可以放入物品的重量为s，现有n件物品，重量分别为w[0],w[1],……,w[n-1]。
问题是能否从这n件物品中选择若干件放入此背包中使得放入的重量之和正好等于s。
如果存在一种符合上述要求的选择，则称此问题有解；
否则称此问题无解。试用分而治之的算法设计方法设计求解背包问题的函数。*/

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define sl system("cls")		//定义系统清屏函数的宏
#define ff fflush(stdin)		//定义清除缓存函数的宏
   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<<"请按任意字母键继续 "<<endl;
	cin>>s;
//ff;
//sl;
}
 int w[100];  //:存放n件物品的重量
 int s=-1,n=-1;    // s:背包中所能承受的物品总重量 n:物品的数量
void input()
{  //用户输入问题的相关数据并对数据排序
    int i,j,t;//i，j,k,t：临时变量
    cout<<"The number of object:" ;
	while(n<0)
	{
	  cin>>n;
	if(n<0)cout<<"物品件数不能为负数或0请输入正确的数据，谢谢合作！"<<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];
	//用选择法排序将这些数从大到小排序
	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;
}