购物单（算法课设题目）（动态规划，深度优先，背包问题）

* \ 小明的妈妈奖励他N元，小明开始做预算，给出m件物品的价格以及重要度，
 * \ 小明想在不超过N元的前提下，使得购买的物品的价格与重要度的乘积
 * \ 的总和最大

 * anaysis：
            明显可以定义出一个结构体来存储每件商品的信息，然后就可以用深度优先搜索
            算法进行选择
   DFS 函数:  DFS_select(int index,int sum_price,int sum_value);

/** \brief
 *
 * \ 小明的妈妈奖励他N元，小明开始做预算，给出m件物品的价格以及重要度，
 * \ 小明想在不超过N元的前提下，使得购买的物品的价格与重要度的乘积
 * \ 的总和最大
 * anaysis：
            明显可以定义出一个结构体来存储每件商品的信息，然后就可以用深度优先搜索
            算法进行选择
   DFS 函数:  DFS_select(int index,int sum_price,int sum_value);
   data:    120
            5
            30 40 55 25 80
            5 4 5 3 4
            or
            120
            5
            30 40 55 25 80
            5 3 5 3 4
 */
 
 
#include <iostream>
#include <vector>
using namespace std;
struct item
{
    int price,impor,value;
};
void DFS_select(int index,int sum_price,int sum_value);
int money,item_size,max_value=-1;
vector<item> items;
vector<int> ans,temp;
int main()
{
    cout << "输入妈妈给小明多少钱:\n";
    int flag=0;
    do
    {
        if(flag)
            cout << "请重新输入正确的钱的数量:\n";
        flag=1;
        cin >> money;
    }while(money<0);
    cout << "输入商品的数量：\n";
    flag=0;
    do
    {
        if(flag)
            cout << "请重新输入正确的商品的数量:\n";
        flag=1;
        cin >> item_size;
    }while(item_size<=0);
    item temp;
    cout << "输入 " << item_size << " 件商品的价格:\n";
    for(int i=0;i<item_size;++i)
    {
        cin >> temp.price;
        items.push_back(temp);
    }
    cout << "输入 " << item_size << " 件商品的重要度:\n";
    for(int i=0;i<item_size;++i)
    {
        cin >> temp.impor;
        items[i].impor=temp.impor;
        items[i].value=temp.impor*items[i].price;
    }
    DFS_select(0,0,0);
    cout << "max_value is " << max_value << endl;
    cout << "select index of items are :\n";
    for(auto a:ans)
        cout << a+1 << ' '; //< 商品下标从1开始
    cout << endl;
    return 0;
}
 
void DFS_select(int index,int sum_price,int sum_value)
{
    if(index>item_size||sum_price>money)
        return;
    if(sum_price<=money&&sum_value>max_value)
    {
        max_value=sum_value;
        ans=temp;
    }
//    这儿我感觉是可以改进一下的
//    temp.push_back(index);
//    DFS_select(index+1,sum_price+items[index].price,sum_value+items[index].value);
//    temp.pop_back();
//    DFS_select(index+1,sum_price,sum_value);
 
    temp.push_back(index);
    if(sum_price+items[index].price<=money)
        DFS_select(index+1,sum_price+items[index].price,sum_value+items[index].value);
    temp.pop_back();    //< 回溯，不选择index号商品
    DFS_select(index+1,sum_price,sum_value);
}

* \  2)其实现在细细想来，这不就是属于背包问问题吗，emm，确实是这样，后面再用
     动态规划解决试试
*/

/**
    动态规划 solution
*/

/**
    1)用一维数组来存储状态信息，但显然这无法知道选择了哪几件商品，
      因此后面我用了二维数组来存储状态信息。

/**
* \  2)其实现在细细想来，这不就是属于背包问问题吗，emm，确实是这样，后面再用
     动态规划解决试试
*/
/**
    动态规划 solution
*/
/**
    1)用一维数组来存储状态信息，但显然这无法知道选择了哪几件商品，
      因此后面我用了二维数组来存储状态信息。
      dp[i][v]=max(dp[i-1][v],dp[i-1][v-items[i].price]+items[i].value);
      当dp[i][v]==dp[i-1][v]时，说明没选择第i件物品，否则选择了。
*/
/**
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
struct item
{
    int price,impor,value;
};
int money,item_size,max_value=-1;
vector<item> items;
int main()
{
    cout << "输入妈妈给小明多少钱:\n";
    int flag=0;
    do
    {
        if(flag)
            cout << "请重新输入正确的钱的数量:\n";
        flag=1;
        cin >> money;
    }while(money<0);
    cout << "输入商品的数量：\n";
    flag=0;
    do
    {
        if(flag)
            cout << "请重新输入正确的商品的数量:\n";
        flag=1;
        cin >> item_size;
    }while(item_size<=0);
    item temp;
    cout << "输入 " << item_size << " 件商品的价格:\n";
    for(int i=0;i<item_size;++i)
    {
        cin >> temp.price;
        items.push_back(temp);
    }
    cout << "输入 " << item_size << " 件商品的重要度:\n";
    for(int i=0;i<item_size;++i)
    {
        cin >> temp.impor;
        items[i].impor=temp.impor;
        items[i].value=temp.impor*items[i].price;
    }
    int dp[money+1];
    memset(dp,0,sizeof(dp));//边界设计
    for(int i=0;i<item_size;++i)
        for(int v=money;v>=items[i].price;--v)//应当是从右至今开始递推，和01背包问题一样
        {
            dp[v]=max(dp[v],dp[v-items[i].price]+items[i].value);
        }
 
    cout << dp[money] << endl;
    return 0;
}
*/

/**
    3)二维数组记录状态信息
    anaysis:
    状态设计：dp[i][v]表示选择前i件商品，花了v元的重要度；
    状态转移方程： dp[i][v]=max(dp[i-1][v],dp[i-1][v-items[i].price]+items[i].value);
      当dp[i][v]==dp[i-1][v]时，说明没选择第i件物品，否则选择了。
*/

/**
    3)二维数组记录状态信息
    anaysis:
    状态设计：dp[i][v]表示选择前i件商品，花了v元的重要度；
    状态转移方程： dp[i][v]=max(dp[i-1][v],dp[i-1][v-items[i].price]+items[i].value);
      当dp[i][v]==dp[i-1][v]时，说明没选择第i件物品，否则选择了。
*/
/**
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
struct item
{
    int price,impor,value;
};
 
int main()
{
    int money,item_size;
    cout << "输入妈妈给小明多少钱:\n";
    int flag=0;
    do
    {
        if(flag)
            cout << "请重新输入正确的钱的数量:\n";
        flag=1;
        cin >> money;
    }while(money<0);
    cout << "输入商品的数量：\n";
    flag=0;
    do
    {
        if(flag)
            cout << "请重新输入正确的商品的数量:\n";
        flag=1;
        cin >> item_size;
    }while(item_size<=0);
    item infor;
    vector<item> items;
    cout << "输入 " << item_size << " 件商品的价格:\n";
    for(int i=0;i<item_size;++i)
    {
        cin >> infor.price;
        items.push_back(infor);
    }
    cout << "输入 " << item_size << " 件商品的重要度:\n";
    for(int i=0;i<item_size;++i)
    {
        cin >> infor.impor;
        items[i].impor=infor.impor;
        items[i].value=infor.impor*items[i].price;
    }
    int dp[item_size+1][money+1];
    for(int i=0;i<=money;++i)
        dp[0][i]=0; //边界设计
    for(int i=1;i<=item_size;++i)
    {
        for(int v=0;v<items[i-1].price;++v)
            dp[i][v]=dp[i-1][v];
        for(int v=items[i-1].price;v<=money;++v)
        {
            dp[i][v]=max(dp[i-1][v],dp[i-1][v-items[i-1].price]+items[i-1].value);
        }
    }
 
    int choose[item_size+1],temp=money;
    for(int i=item_size;i>0;--i)
    {
        if(dp[i][temp]==dp[i-1][temp])
            choose[i]=0;
        else
        {
            choose[i]=1;
            temp-=items[i-1].price;
        }
    }
    cout << "max_value is " << dp[item_size][money] << endl;
    cout << "select index of items are :\n";
    for(int i=1;i<=item_size;++i)
        if(choose[i]==1)
            cout << i << ' '; //< 商品下标从1开始
    cout << endl;
    return 0;
}
*/

/**
    再编码：商品下标从1开始，思想和上一个代码一摸一样；
*/

 
/**
    再编码：商品下标从1开始，思想和上一个代码一摸一样；
*/
 
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
struct item
{
    int price,impor,value;
};
 
int main()
{
    int money,item_size;
    cout << "输入妈妈给小明多少钱:\n";
    int flag=0;
    do
    {
        if(flag)
            cout << "请重新输入正确的钱的数量:\n";
        flag=1;
        cin >> money;
    }while(money<0);
    cout << "输入商品的数量：\n";
    flag=0;
    do
    {
        if(flag)
            cout << "请重新输入正确的商品的数量:\n";
        flag=1;
        cin >> item_size;
    }while(item_size<=0);
    //item infor;
    vector<item> items(item_size+1);
    cout << "输入 " << item_size << " 件商品的价格:\n";
    for(int i=1;i<=item_size;++i)
    {
        cin >> items[i].price;
    }
    cout << "输入 " << item_size << " 件商品的重要度:\n";
    for(int i=1;i<=item_size;++i)
    {
        cin >> items[i].impor;
        items[i].value=items[i].impor*items[i].price;
    }
    int dp[item_size+1][money+1];
    for(int i=0;i<=money;++i)
        dp[0][i]=0; //边界设计
    for(int i=1;i<=item_size;++i)
    {
        for(int v=0;v<items[i].price;++v)
            dp[i][v]=dp[i-1][v];
        for(int v=items[i].price;v<=money;++v)
        {
            dp[i][v]=max(dp[i-1][v],dp[i-1][v-items[i].price]+items[i].value);
        }
    }
 
    int choose[item_size+1],temp=money;
    for(int i=item_size;i>0;--i)
    {
        if(dp[i][temp]==dp[i-1][temp])
            choose[i]=0;
        else
        {
            choose[i]=1;
            temp-=items[i].price;
        }
    }
    cout << "max_value is " << dp[item_size][money] << endl;
    cout << "select index of items are :\n";
    for(int i=1;i<=item_size;++i)
        if(choose[i]==1)
            cout << i << ' '; //< 商品下标从1开始
    cout << endl;
    return 0;
}