#刷题##动态规划##0-1背包问题#——购物单问题（C++）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• 一、购物单问题描述
• 二、0-1背包问题
• 三、如何解决这个不同
• 四、代码思路
• 五、代码

• 一人手握定量的钱，要去购买物品；
• 物品分主件、附件（每个主件最多有两个附件），若要购买附件的话，则必须够买主件，购买主件不一定需要购买附件；
• 物品有三个参数：价格、重要度、区别物品是主件附件的参数。

输入：

• 输入的第 1 行，为两个正整数M、N，用一个空格隔开； 其中 M表示总钱数， N为可购买的物品的个数；
  此处的N不意味着必须购买N个物品，而是代表主件、附件加起来，输入的一共有N种物品。
• 从第 2 行到第 N+1 行，每行输入三个参数。第一个参数为价格，第二个参数为重要度，第三个参数表明其为主件或附件。
  第三个参数若为0，则表明其为主件，若不为0，则表明其是参数对应主件的附件。

输出：

• 输出一个正整数，输出可以获得的最大的满意度。

购物单问题与0-1背包问题相似，不过略微复杂一些，因此先来看看0-1背包问题

背包问题描述：

• 有一个背包可以装物品的总重量为W，现有N个物品，每个物品中w[i]，价值v[i]，用背包装物品，能装的最大价值是多少？

解题思路：

• 状态转移数组：定义状态转移数组dp[i][j]：前i个物品，背包重量为j，能装下的最大价值

• dp[i][j] = max(dp[i - 1][j - v[i]] + v[j], dp[i-1][j])
  购物单问题与0-1背包问题的不同：

• 背包问题中，是否选择物品只取决于其的重量与价值，在购物单问题中，如果对应的主件不存在则不能购买附件

• 既然附件的选择较为复杂，不妨从主件入手，当选择某个主件后，最终选择可能存在四种情况：

• 1. 仅主件，无附件
• 2. 主件，附件1
• 3. 主件，附件2
• 4. 主件，附件1，附件2

• 图像化想象，用容器存储物品：

每个物品有价格、重要度两个参数，所以会有两张表：价格表、价值表

• 显然需要两个容器，分别设置为

vector> price(N+1, vector(3, 0));
vector> value(N+1, vector(3, 0));
//每个容器大小为N+1，每一个主件占一个位置，容器中所存储的元素为vector
//vector的大小为3，vector中3个元素的初始值均为0，每个元素中再包含附件

• 状态转移数组

//dp[i][j]表示在钱数不超过j的情况下，对前i件产品进行选择，所能获得的最大重要度
dp[i][j] = max(dp[i-1][j-value[i]]+value[i], dp[i-1][j])
//为了提高时间复杂度，将当前物品价格与j进行比较，若其大于j，dp[i][j]=dp[i-1][j]
dp[i][j] = max(不买主件k,买主件k,买主件k和附件1,买主件k和附件2,买主件和附件1、2)

1. 输入总钱数、物品个数
2. 设计容器，将物品的信息输入
3. 从第一个主件开始，每有一个主件就进行一轮比较（外部循环，循环条件是还有主件没遍历）
4. 在外部循环里，有循环嵌套，针对dp[i][j]中的j，从10,20,30…直到N

#include 
#include 
using namespace std;

int main()
{
    int M,N;  //总钱数，供选择物品的个数
    cin >> M >> N;
    M /= 10;  //总钱数为10的整数倍，本算法中所有price都表示为price/10
    
    vector> price(N+1, vector(3, 0));  //vector(int size, const &t)
    vector> value(N+1, vector(3, 0));  //容器容量为size，里面存储的值是t
    
    //输入物品的基本数据
    for(int i = 1; i <= N; ++i)  
    {
        int a,b,c;
        cin >> a >> b >> c;
        if(c == 0)  //若该物品为主件
        {
            price[i][0] = a / 10;  //将价格存入
            value[i][0] = b;  //将价值存入
        }
        else if(price[c][1] == 0) //该物品为附件,且是第一个附件
        {
            price[c][1] = a / 10;
            value[c][1] = b;
        }
        else  //该物品为附件，且之前已经有一附件，这是第二个附件
        {
            price[c][2] = a / 10;
            value[c][2] = b;
        }
    }
    
    vector> dp(N+1, vector(M+1, 0));
    for(int i = 1; i <= N; ++i)
    {
        for(int j = 1; j <= M; ++j)
        {
            int a = price[i][0], b = value[i][0];
            int c = price[i][1], d = value[i][1];
            int e = price[i][2], f = value[i][2];
            dp[i][j] = j >= a ? max(dp[i-1][j-a] + (a*b), dp[i-1][j]) : dp[i-1][j];
            dp[i][j] = j >= (a+c) ? max(dp[i-1][j-a-c] + (a*b+c*d), dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (a+e) ? max(dp[i-1][j-a-e] + (a*b+e*f), dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (a+c+e) ? max(dp[i-1][j-a-c-e] + (a*b+c*d+e*f), dp[i][j]) : dp[i][j];
        }
    }
    
    cout << dp[N][M]*10 << endl; 
    return 0;
}