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

/**< 1th example) */
/** \brief
 * 在九件物品中选出3件使其重量和500克之差的绝对值最小
 * \求出物体编号
 * \param
 * \return
 *
 */
/**< 循环求解，循环求解只能处理选择特定的物品数量，不具有普遍性； */

/**< 1th example) */
/** \brief
 * 在九件物品中选出3件使其重量和500克之差的绝对值最小
 * \求出物体编号
 * \param
 * \return
 *
 */
/**< 循环求解 */

#include <iostream>
#include <cstdio>
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)<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
 * 在n件物品中选出k件使其重量和500克之差的绝对值最小
 * \求出物体编号
 * \param
 * \return
 *
 */
/**< 深度优先搜索求解 */

/** \brief
 * 在n件物品中选出k件使其重量和500克之差的绝对值最小
 * \求出物体编号
 * \param
 * \return
 *
 */
/**< 深度优先搜索求解 */

/**
#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 << "输入物品的总数量以及要选择的物品数量:\n";
    cin >> n >> sum;
    cout << "输入" << n << "件物品的重量:\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)//< 这里不能加绝对值
        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)  //这样能稍微节约一点时间，不至于每个物品都去选择
        DFS(index+1,sum+1,weight+matr[index]);  //因为abs_cha一定是一个非负数，当weight+matr[index]-500
    temp.pop_back();                            //比abs_cha还大时，那么这个组合一定不是最佳选择的组合
    DFS(index+1,sum,weight);
}
*/

/**< 2th example */
/** \brief
 * 有一个背包可以放入的物品重量为S，现有n件物品，
 * \ 问能否从这n件物品中选择若干件放入背包，使得放入的
 * \ 重量之和恰为S
 * \return
 *
 */

 /** \brief 递归设计分析
  * Knap(s,n)表示背包的容量还剩余s，还有n件物品没进行选择
  * \
  * \param
  * \return
  *
  */

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

/**< 2th example */
/** \brief
 * 有一个背包可以放入的物品重量为S，现有n件物品，
 * \ 问能否从这n件物品中选择若干件放入背包，使得放入的
 * \ 重量之和恰为S
 * \return
 *
 */

 /** \brief 递归设计分析
  * Knap(s,n)表示背包的容量还剩余s，还有n件物品没进行选择
  * \
  * \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 << "输入物品数量及背包容量:\n";
    cin >> n >> s;
    cout << "输入" << n<< "件物品的重量:\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) //选择第unselected件物品
    {
        cout << "choose : " << unselected << "th" << endl;
        return true;
    }
    else
        return Knap(rest,unselected-1);//不选择第unselected件物品
}

/**< 2th example */
/** \brief
 * 有一个背包可以放入的物品重量为S，现有n件物品，
 * \ 问能否从这n件物品中选择若干件放入背包，使得放入的
 * \ 重量之和恰为S
 * \return
 *
 */

 /** \brief 深度优先搜索分析
  * Knap(index,sum_value)表示此时对第index件物品进行选择，已选择的物品
  * \ 重量为sum_value
  * \param
  * \return
  *
  */

/**< 2th example */
/** \brief
 * 有一个背包可以放入的物品重量为S，现有n件物品，
 * \ 问能否从这n件物品中选择若干件放入背包，使得放入的
 * \ 重量之和恰为S
 * \return
 *
 */

 /** \brief 深度优先搜索分析
  * Knap(index,sum_value)表示此时对第index件物品进行选择，已选择的物品
  * \ 重量为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 << "输入物品数量及背包容量:\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<ans.size();++i)
    {
       cout << "choose " << ans[i] << "th\n";
    }
}