Knapsack problem unrelated to profit (depth first search)

/**< 1th example) */
/** \brief
 * Choose from nine items 3 Make its weight equal to 500 The absolute value of the difference between grams is the smallest
 * \ Find the object number
 * \param
 * \return
 *
 */
/**< Loop solution , Loop solving can only deal with selecting a specific number of items , Not universal ; */

/**< 1th example) */
/** \brief
 *  Choose from nine items 3 Make its weight equal to 500 The absolute value of the difference between grams is the smallest 
 * \ Find the object number 
 * \param
 * \return
 *
 */
/**<  Loop solution  */

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int n=9,abs_cha=1000;
    int matr[n+1];
    cout << " Input " << n << " The weight of an item :\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)<abs_cha)
                {
                    bestw=temp_sum;
                    abs_cha=abs(temp_sum-500);
                    besti=i;
                    bestj=j;
                    bestk=k;
                }
            }
    printf("choose index is : %d %d %d \n",besti,bestj,bestk);
    printf("best weight is:%d",bestw);
    return 0;
}

/** \brief
 * stay n Choose from items k Make its weight equal to 500 The absolute value of the difference between grams is the smallest
 * \ Find the object number
 * \param
 * \return
 *
 */
/**< Depth first search solution */

/** \brief
 *  stay n Choose from items k Make its weight equal to 500 The absolute value of the difference between grams is the smallest 
 * \ Find the object number 
 * \param
 * \return
 *
 */
/**<  Depth first search solution  */

/**
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> ans,temp;
int bestw=0,abs_cha=1000;
int matr[10];
void DFS(int index,int sum,int weight);
int main()
{
    int n,sum;
    cout << " Enter the total number of items and the number of items to select :\n";
    cin >> n >> sum;
    cout << " Input " << n << " The weight of an item :\n";
    for(int i=1;i<=n;++i)
        cin >> matr[i];
    DFS(1,0,0);
    printf("choose index is : \n");
    for(size_t i=0;i<ans.size();++i)
        cout << ans[i] << ' ';
    cout << endl;
    printf("best weight is:%d",bestw);
    return 0;
}

void DFS(int index,int sum,int weight)
{
    if(index>9||sum>3||abs_cha<weight-500)//<  Absolute value cannot be added here 
        return;
    if(sum==3)
    {
        if(abs_cha>abs(weight-500))
        {
            ans=temp;
            bestw=weight;
            abs_cha=abs(weight-500);
        }
        return;
    }
    temp.push_back(index);
    if(weight+matr[index]-500<abs_cha)  // This will save a little time , Not every item should be chosen 
        DFS(index+1,sum+1,weight+matr[index]);  // because abs_cha It must be a non negative number , When weight+matr[index]-500
    temp.pop_back();                            // Than abs_cha When I was young , Then this combination must not be the best choice 
    DFS(index+1,sum,weight);
}
*/

/**< 2th example */
/** \brief
 * There is a backpack that can hold items weighing S, existing n Item ,
 * \ Ask if it's possible to n Select several items from the items and put them into the backpack , Make it put in
 * \ The sum of the weights is just S
 * \return
 *
 */

 /** \brief Recursive design analysis
  * Knap(s,n) Indicates that the capacity of the backpack is still left s, also n Items are not selected
  * \
  * \param
  * \return
  *
  */

This recursive function is quite good , Output subscripts directly in recursive functions , You can learn . This is seen in the textbook of algorithm design and analysis .

/**< 2th example */
/** \brief
 *  There is a backpack that can hold items weighing S, existing n Item ,
 * \  Ask if it's possible to n Select several items from the items and put them into the backpack , Make it put in 
 * \  The sum of the weights is just S
 * \return
 *
 */

 /** \brief  Recursive design analysis 
  * Knap(s,n) Indicates that the capacity of the backpack is still left s, also n Items are not selected 
  * \
  * \param
  * \return
  *
  */


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

int main()
{
    int n;
    double s;
    cout << " Enter the number of items and backpack capacity :\n";
    cin >> n >> s;
    cout << " Input " << n<< " The weight of an item :\n";
    for(int i=1;i<=n;++i)
        cin >> matr[i];
    if(Knap(s,n)==false)
        cout << "No solution\n";
    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) // Select the first unselected Item 
    {
        cout << "choose : " << unselected << "th" << endl;
        return true;
    }
    else
        return Knap(rest,unselected-1);// No choice unselected Item 
}

/**< 2th example */
/** \brief
 * There is a backpack that can hold items weighing S, existing n Item ,
 * \ Ask if it's possible to n Select several items from the items and put them into the backpack , Make it put in
 * \ The sum of the weights is just S
 * \return
 *
 */

 /** \brief Depth first search analysis
  * Knap(index,sum_value) Indicates that at this time, it is right for index Select items , Selected items
  * \ Weight is sum_value
  * \param
  * \return
  *
  */

/**< 2th example */
/** \brief
 *  There is a backpack that can hold items weighing S, existing n Item ,
 * \  Ask if it's possible to n Select several items from the items and put them into the backpack , Make it put in 
 * \  The sum of the weights is just S
 * \return
 *
 */

 /** \brief  Depth first search analysis 
  * Knap(index,sum_value) Indicates that at this time, it is right for index Select items , Selected items 
  * \  Weight is sum_value
  * \param
  * \return
  *
  */


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

    cout << " Enter the number of items and backpack capacity :\n";
    cin >> n >> s;
    cout << " Input " << n<< " The weight of an item :\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<ans.size();++i)
    {
       cout << "choose " << ans[i] << "th\n";
    }
}