背包问题（非递归）.cpp

背包问题的非递归解法

// 背包问题（非递归）.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;
}