与利润无关的背包问题（深度优先搜索）

#include 
#include 
using namespace std;

int main()
{
    int n=9,abs_cha=1000;
    int matr[n+1];
    cout << "输入" << n << "件物品的重量:n";
    for(int i=1;i<=n;++i)
        cin >> matr[i];
    int besti,bestj,bestk;
    int bestw,temp_sum=0;
    for(int i=1;i<=7;++i)
        for(int j=i;j<=8;++j)
            for(int k=j;k<=9;++k)
            {
                temp_sum=matr[i]+matr[j]+matr[k];
                if(abs(temp_sum-500)

 
 
 
 
这个递归函数蛮不错的，直接在递归函数里输出下标，可以学习学习。这是在算法设计与分析教材上看的。
 


 


#include 
using namespace std;
const int maxn=10;
int matr[maxn];
bool Knap(double rest,int unselected );

int main()
{
    int n;
    double s;
    cout << "输入物品数量及背包容量:n";
    cin >> n >> s;
    cout << "输入" << n<< "件物品的重量:n";
    for(int i=1;i<=n;++i)
        cin >> matr[i];
    if(Knap(s,n)==false)
        cout << "No solutionn";
    return 0;
}

bool Knap(double rest,int unselected )
{
    if(rest==0)
        return true;
    else if(rest<0||(rest>0&&unselected<1))
        return false;
    else if(Knap(rest-matr[unselected],unselected-1)==true) //选择第unselected件物品
    {
        cout << "choose : " << unselected << "th" << endl;
        return true;
    }
    else
        return Knap(rest,unselected-1);//不选择第unselected件物品
}
 
 
 


 
 
 
 



 


#include 
#include 
using namespace std;
const int maxn=10;
int matr[maxn];
int n;
double s;
vector ans,temp;
void Knap(int index,double sum_value);
void output();
int pos=1;
int main()
{

    cout << "输入物品数量及背包容量:n";
    cin >> n >> s;
    cout << "输入" << n<< "件物品的重量:n";
    for(int i=1;i<=n;++i)
        cin >> matr[i];
    Knap(1,0);

    return 0;
}


void Knap(int index,double sum_value)
{
    if(index>n||sum_value>s)
        return;
    if(sum_value==s)
    {
        ans=temp;
        output();
        return ;
    }
    temp.push_back(index);
    if(sum_value+matr[index]<=s)
        Knap(index+1,sum_value+matr[index]);
    temp.pop_back();
    Knap(index+1,sum_value);
}

void output()
{
    cout << pos++ << "th:n";
    for(size_t i=0;i