首先看一下题
描述
王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件 电脑 打印机，扫描仪 书柜 图书 书桌 台灯，文具 工作椅 无 如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。
王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。
满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第i件物品的价格为v[i]，重要度为w[i]，共选中了k件物品，编号依次为j1,j2,...,jk，则满意度为：v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk]。（其中 * 为乘号）
请你帮助王强计算可获得的最大的满意度。
输入描述：
输入的第 1 行，为两个正整数N，m，用一个空格隔开：
（其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
输出描述：
输出一个正整数，为张强可以获得的最大的满意度。
示例1
输入：
1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0输出：
2200示例2
输入：
50 5 20 3 5 20 3 5 10 3 0 10 2 0 10 1 0输出：
130说明：
由第1行可知总钱数N为50以及希望购买的物品个数m为5； 第2和第3行的q为5，说明它们都是编号为5的物品的附件； 第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5； 所以物品的价格与重要度乘积的总和的最大值为10*1+20*3+20*3=130
一、问题分析
1.王强的年终奖N可以用来购物。N<32000
2.王强可以购买物品的数量有上限m个（有m种商品供我们选择而不是只能买m件商品）。m<60
3.购买的物品有重要度p，还有价格v，还有一个特殊的属性q。
4.如果q=0，那么证明这个物品是“主件”，如果q>0那么这个物品是“附件”而q的值是他所属主件的编号。
5.主件的编号从哪来？看我们的输入，第一行是两个整数N和m。从第二行开始是我们的物品vpq，而第二行的物品的编号就是1，第三行物品的编号是2，以此类推，一共有m个物品所以一共有m+1行的输入，物品编号最大是m。这里需要注意的一点就是q。
6.q的值如果不为空，那么q的值就是他所属主件的物品编号，我们如果要买一个“附件”，一定要先买好“主件”。
7.每个物品只能购买一次
8.每个主件可以有0,1,2个附件。（三种情况）
9.附件不再有从属于自己的附件。
10.物品的价格都是10的整数倍。
11.王强希望在花费不超过N的情况下，使自己的满意度达到最大。
12.满意度的计算是所有购买的商品的重要度p*价格v的乘积累加在一起得到的。
13.所以我们买东西的方式不止一种，可以买不同的物品组合，每种方式得到的满意度可能相同，可能不同，但是我们需要找到一种买东西的方式使满意度最大。
14.最终我们输出这个满意度。
二、解题思路
1.数据结构设计
- 我们可以定义一个结构体来表示物品，其中包含了价格、重要度和主附件信息这三个参数。
- 我们可以定义一个数组来存储所有的物品，方便后面的遍历和处理。
2.然后觉得这个问题有点复杂，我们要考虑的有N、p、v、q、m，尝试把问题拆分成小问题
首先我们可以这样想，将物品是否是主件还是附件的问题先不考虑，
先考虑有N元钱，m个物品，每个物品有价格v和重要度p，求最大满意度
然后这个问题我们还可以再拆分一下，先不考虑重要度
先考虑有N元钱，m个物品，每个物品的价格v已知（物品的序号已知且每个物品只能购买一次），求有多少种购买物品的方式
为了实现这一目的我们需要使用动态规划法：
- 动态规划（Dynamic Programming）的起源
- “dp” 是 “Dynamic Programming” 的缩写。这个名称最初是由美国数学家理查德・贝尔曼（Richard Bellman）在 20 世纪 50 年代提出的。当时他在研究多阶段决策过程优化问题时，需要一种有效的方法来记录和利用中间结果，以避免重复计算，于是创造了动态规划这种方法。
- 在代码中的命名传统
- 在计算机编程领域，尤其是在解决动态规划问题时，使用 “dp” 来命名存储中间结果的变量（如数组、矩阵等）已经成为一种广泛接受的命名传统。这是因为这些变量通常用于存储动态规划过程中的 “状态”（state）。
- 例如，在背包问题中，
dp[i][j]可能表示在前i个物品中，背包容量为j时的最优解（如最大价值、最少重量等）。这里的 “dp” 简洁明了地提醒程序员这个变量是用于动态规划算法的中间结果存储，方便代码的阅读和理解。- 方便记忆和识别
- 对于熟悉动态规划的程序员来说，看到 “dp” 这样的命名，就能够快速意识到这段代码可能涉及到动态规划算法，并且能够大致猜测变量的用途。这种命名方式有助于提高代码的可读性和可维护性，特别是在处理复杂的算法逻辑时。
实现这种方法的基础是
当我们每购买一件物品的时候，我们的N会减少购买物品的价格，并且我们的（还没有定义的）购买物品的数量会增加1。
- 定义状态：我们使用dp[i][j]来表示在前i个物品中，花费不超过j元的购买方式总数。
- 状态转移方程：
- 如果不选择第
i个物品，那么dp[i][j] = dp[i - 1][j]，即购买方式总数与不考虑第i个物品时相同。 - 如果选择第
i个物品，需要满足预算足够，即j >= v[i]，此时dp[i][j] += dp[i - 1][j - v[i]]，表示加上不选择第i个物品时，花费j - v[i]元的购买方式总数。
- 如果不选择第
- 初始化：
dp[0][0] = 1，表示没有物品时，花费 0 元有一种方式（什么都不买）；其他dp[0][j] = 0，表示没有物品时，花费非零金额没有购买方式。 - 最终答案为
dp[m][N]，即考虑所有m个物品，预算为N时的购买方式总数。
想到这里我就暂时放弃自己思考了，于是我直接看了题解。。。
#include<stdio.h>
#include<math.h>
int main() {
int money = 0, num = 0;
scanf("%d %d\n", &money, &num);
int v, p, q;
//创建两个二维数组，可以把（主件,主件+附件1,主件+附件2,主件+附件1+附件2）每样看成一个完整物品做动态规划
int weight[num][4];//每个物品的价值（价格*权重）
int cost[num][4];//每个物品的成本（价格）
memset(weight, 0, sizeof(weight));
memset(cost, 0, sizeof(cost));
//初始化数组，添加每个物品的价值和成本,先不要加上主件，如果附件先给出那么因为主件的值还为0，会初始化错误
for (int i = 0; i < num; i++) {
scanf("%d %d %d\n", &v, &p, &q);
if (q == 0) { //如果这个物品不是附件，直接放到数组里
weight[i][0] = v * p;
cost[i][0] = v;
} else if (cost[q - 1][1] ==
0) { //如果是并且是物品q的第一个附件，(第一次提交的错误：加上主件的成本还有价值放到组组里)
weight[q - 1][1] = v * p;
cost[q - 1][1] = v;
} else { //如果是并且是物品q的第二个附件，同上
weight[q - 1][2] = v * p;
cost[q - 1][2] = v;
weight[q - 1][3] = v * p + weight[q - 1][1];
cost[q - 1][3] = v + cost[q - 1][1];
}
}
//所以需要重新加主件一次（初始化的时候就不用加了）
for (int j = 0; j < num; j++) {
if (cost[j][0] != 0 ||
cost[j][1] == 0) { //附件或没有附件的主件就不用加了
for (int k = 1; k < 4; k++) {
weight[j][k] += weight[j][0];
cost[j][k] += cost[j][0];
}
}
}
int dp[money + 1]; //用一维数组做动态规划
memset(dp, 0, sizeof(dp));//所有值初始化为0
for (int x = 0; x < num; x++) {
if (cost[x][0] == 0)
continue; //如果是附件就不用单独买（动态规划剪枝）
for (int y = money; y > 0; y -= 10) {
for (int z = 0; z < 4; z++) {
if (y >= cost[x][z]) { //买完钱有富余或正好可以买下时
dp[y] = fmax(dp[y], weight[x][z] + dp[y -
cost[x][z]]); //把当前的最大值放到数组里
}
}
}
}
printf("%d\n", dp[money]);
}以上是一个验证过可以通过的代码
我们来分析一下这个代码为什么可以成功计算满意度
首先定义了money和num这样可以直观地知道我们拥有的钱数（预算）和物品的数量
然后定义了v价格，p重要度，q是否是附件（或者所属主件编号）。
然后定义了一个二维数组weight[num][4]用来存储物品的价值（价格*重要度）这个二维数组中的num用来表示物品的编号
而4呢，这个4是用来表示这个物品是主件还是附件的，0表示主件，1表示第一个附件，2表示是第二个附件，3表示第一个和第二个附件。
| 编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | ||||
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 |
还定义了另一个二维数组cost[num][4]用来存储物品的价格（成本），我们不是每个物品都有一个价格吗？那定义一个普通的数组不就完了么为什么还需要二维数组呢？这是因为我们考虑到了主附件的问题从0到3分别表示不同的组合方式，单主件，主件+附件1，主件+附件2，主件+附件1+附件2这四种情况。
定义完二维数组时候别忘用了memset初始化我们的数组，memset使用方式是，先#include <string.h>库， memeset（要填充的内存块的起始地址的指针，要设置的值，要填充的字节数）
在这里我们将weight和cost全部填充为0，要填充的字节数就是他们自己的大小
| 编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
然后我们要将数据读取到我们的vpq中然后储存到数组中，
我们使用for循环，然后设定一个i=0记录我们读取的物品编号，条件是i<num当没有读取完所有的物品的情况下，继续循环，然后每次循环结束我们的i++增加1，证明我们是一行一行读取的
for(int i = 0; i<num; i++)
之后呢我们scanf("%d %d %d\n", &v, &p, &q);
读取完物品的vpq之后我们需要将他们储存到我们的weight和cost中
那么如何储存？
首先我们的weight=v*p，我们的cost=v
然后我们思考，如何区分主附件？
如果q==0那么证明是主件，这样的话我们可以使用if条件来判断
如果是主件，就将他直接放到数组中，主件的价值就是价格*重要度，主件的价格就是价格
如果不是主件，这时候都有哪些情况？
我们的q不等于0时，证明不是主件，那么我们的q等于几号，编号几的物品就是他的主件
这个时候我们将这个位置的物品的weight和cost保留为0（因为是附件，不能单独购买所以我们只有在购买了主件的前提之下才会购买附件，这样的话我们就将所有的附件都保存在主件的列索引上就行了）
然后我们查看主件的第二列的cost，如果是0证明我们找到的是主件的第一个附件或者之前的附件价格为0因为0*任何数都得0这种情况我们可以认为已经考虑到了。这个时候我们将主件的第二列的weight和cost记录一下。
如果我们的主件第二列的cost算出来不是0的情况下，证明是第二个附件
此时我们将第二个附件的weight和cost存储到主件的第三列中，然后第四列存储
第二列和第三列的和，用来表示第一个附件和第二个附件都购买的情况。
示例1
输入：
1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0
比如示例1中的输入保存在我们的weight[num][4]中就是weight[5][4]，其中5是物品的数量也是我们的二维数组的行数，4是我们的列数用来表示不同的主附件组合
| 编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
当读取到第一个行800 2 0时，我们的q==0，所以直接储存在weight[i][0]中，因为i现在是0所以我们保存在weight[0][0]中，他的值是v * p也就是800 * 2=1600
| weight表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 1600 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
我们的另外一个二维数组则直接储存v的值
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
然后我们读取第二行（也就是第二个物品的参数）400 5 1，这个时候我们发现q等于0不成立，证明这是一个附件，我们再查看对应主件的第一列的值，如果是0证明这是我们此主件的第一个附件
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
标记为红色的0是我们的主件（因为在c语言中从0开始计算所以编号为1的主件其实储存在我们的cost[0]中（而不是cost[1]））标记为蓝色的0是我们的主件的第一列，用来表示我们的附件的cost值，现在是0，证明我们还没有储存过附件的信息，那我们刚好把这个附件的信息储存进去
这个附件的weight是400*5=2000，cost是400
于是我们得到了
| weight表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 1600 | 2000 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 400 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
接着往下读，第三行是300 5 1，这个时候q等于0不成立，所以证明这是一个附件，而这个附件的主件编号是1，那么我们查看编号为1的主件的第一列是否是0时发现不为0
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 400 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
标记为红色的是我们的编号为1的主件，（实际在数组中的位置是0），他的第二列的数值是400，这证明了我们已经读取过第一个附件了，那么我们此时读取的是他的第二个（也是最后一个附件）
所以我们更新主件的第三列和第四列（分别代表只购买主件和附件2和购买主件和全部附件）
第三列的weight是300*5=1500，cost是300，第四列的weight是2000+1500=3500，cost是400+300=700
| weight表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 1600 | 2000 | 1500 | 3500 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 400 | 300 | 700 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
接下来我们读取第四行（第四个物品（但是其实编号是3）），400 3 0，它的q为0所以我们直接储存到编号4中去就行了，它的weight是400*3=1200，cost是400
| weight表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 1600 | 2000 | 1500 | 3500 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 1200 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 400 | 300 | 700 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 400 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
最后我们读取我们的第五行500 2 0，他的q为0，我们直接储存在主件的位置就行了（编号是5的第一列），它的weight是500*2=1000，cost是500
| weight表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 1600 | 2000 | 1500 | 3500 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 1200 | 0 | 0 | 0 |
| 4 | 1000 | 0 | 0 | 0 |
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 400 | 300 | 700 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 400 | 0 | 0 | 0 |
| 4 | 500 | 0 | 0 | 0 |
读取完全部的物品之后我们还需要更新一下主件的第二三四列的价格（将他们加上主件的价格才是我们购买整个组合的价格）(为什么我们不直接在第一次遍历的时候就加上主件的价格呢？因为我们主件出现的顺序是不一定的，有可能到后面才出现，而我们判断是否要加上主件的价格的条件是主件的价格不为0，所以我们后面再将组合加上主件的价格)
这里使用一个for循环遍历我们的物品，如果物品第一列价格不为0（证明是主件）或者第二列价格为0那么我们附件的weight和cost都增加主件那么多
| weight表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 1600 | 2000+1600=3600 | 1500+1600=3100 | 3500+1600=5100 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 1200 | 1200 | 1200 | 1200 |
| 4 | 1000 | 1000 | 1000 | 1000 |
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 400+800=1200 | 300+800=1100 | 700+800=1500 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 400 | 400 | 400 | 400 |
| 4 | 500 | 500 | 500 | 500 |
之后我们创建一个二维数组dp用于动态规划，存储在不同预算下能获得的最大满意度，并初始化为0.
int dp[money+1];
memset(dp, 0, sizeof(dp));
| dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | dp[6] | dp[7] | ... | dp[money+1] |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
然后我们遍历物品，对于每一个物品x，从x=0开始,当x小于物品总数num时，每次x值增加1x++
如果物品是附件（cost[x][0] == 0）如果物品的第一列是0那么他是一个附件，我们不用单独购买。
然后我们遍历预算，对于预算y=money来说，当我们的预算y>0时，我们循环，每次循环y减少10（因为每件物品的价格是10的整数倍），所以我们不会漏买东西
然后我们遍历物品的四种组合，对于z=0，z<4,每次进入下一个组合
然后我们判断我们剩余的预算y如果大于等于cost[x][z]（x表示当前物品，z表示当前组合），证明我们有预算可以购买这种组合，这种情况下我们的
dp[y] = fmax(dp[y], weight[x][z] + dp[y-cost[x][z]]);
fmax函数会帮助我们选择（a,b）中比较大的一个
所以如果我们的剩余预算买了当前物品的当前组合的话，那么对于我们的当前剩余预算y，
我们求dp[y]也就是最大满意度为，之前的剩余预算为y时的最大满意度和现在这种情况下购买的组合的满意度与之前的减去我们购买物品组合价格之后的预算能达到的最大满意度相加得到的满意度的和，两个数值作比较，选择较大的更新为最大满意度。
举例来说
我们x=0时，
先判断cost[x][0]是否为0，cost[0][0]
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 1200 | 1100 | 1500 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 400 | 400 | 400 | 400 |
| 4 | 500 | 500 | 500 | 500 |
等于800，我们继续往下运行
y=money=1000时
z=0时
我们判断y>=cost[x][z],此时我们的y是1000，x是0，z是0
1000>=cost[0][0]
1000>=800答案是是
于是我们更新我们的dp[y]=fmax(dp[y],weight[x][z]+dp[y-cost[x][z]]);
dp[1000] = fmax(dp[1000],weight[0][0]+dp[1000-cost[0][0])
| weight表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 1600 | 2000+1600=3600 | 1500+1600=3100 | 3500+1600=5100 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 1200 | 1200 | 1200 | 1200 |
| 4 | 1000 | 1000 | 1000 | 1000 |
| dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | dp[6] | dp[7] | ... | dp[1000] |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
dp[1000] = fmax(0, 1600+dp[1000-800])
dp[1000] = fmax(0,1600+dp[200])
dp[1000] = fmax(0,1600+0)
dp[1000] = fmax(0,1600)
dp[1000] = 1600
| dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | dp[6] | dp[7] | ... | dp[1000] |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1600 |
此时我们更新我们的dp为1600
接着，此时我们的z增加了1，
我们继续来判断if(y>=cost[x][z])
这个时候唯一改变的就是z，变成1了
所以我们判断1000>=cost[0][1]
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 1200 | 1100 | 1500 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 400 | 400 | 400 | 400 |
| 4 | 500 | 500 | 500 | 500 |
1000>=1200
判断为否，不执行动作，接下来z++，
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 1200 | 1100 | 1500 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 400 | 400 | 400 | 400 |
| 4 | 500 | 500 | 500 | 500 |
两次，分别他们的价格都超过了我们的预算，所以都不考虑购买
继续z++，当我们z=4的时候，我们的y-=10，此时我们的y变成了990
然后我们先判断if(y>=cost[x][z]),990分别和800,1200,1100,1500比较
结果分别是是,否,否,否,所以我们只在z=0的时候更新我们的dp值
dp[990]=fmax(dp[990],weight[0][0]+dp[990-cost[0][0]]);
dp[990]=fmax(0,1600+dp[990-800])
dp[990]=fmax(0,1600+dp[190])
dp[990]=fmax(0,1600)
dp[990]=1600
| dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | ... | dp[190] | dp[200] | ... | dp[990] | dp[1000] |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1600 | 1600 |
同理我们之后y=980时, 也只能买得起物品一的主件买不起其他的组合,而且dp180....dp0都是0
同理我们的y每次减10,直到减少到800时我们还能买的起物品1的主件,所以我们得到
| dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | dp[6] | dp[7] | ... | dp[800] | ... | dp[1000] |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1600 | 1600 | 1600 |
之后我们的y再减少成790时,因为790<800所以四个组件都买不起,然后我们的y一直减少到0都买不起物品1了
于是我们的x++,进入第二个物品x=1
我们先判断第二个物品是否是附件
if(cost[x][0] == 0) continue;
cost[1][0]
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 1200 | 1100 | 1500 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 400 | 400 | 400 | 400 |
| 4 | 500 | 500 | 500 | 500 |
是附件我们跳过
x++,进入第三个物品x=2
我们先判断第三个物品是否是附件
if(cost[x][0] == 0) continue;
cost[2][0]
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 1200 | 1100 | 1500 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 400 | 400 | 400 | 400 |
| 4 | 500 | 500 | 500 | 500 |
这个也是附件我们再跳过
x++,进入第四个物品x=3
我们判断第四个物品是否是附件
if(cost[x][0] == 0) continue;
cost[3][0]
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 1200 | 1100 | 1500 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 400 | 400 | 400 | 400 |
| 4 | 500 | 500 | 500 | 500 |
cost[3][0] == 0判断失败,我们开始进入y=1000的for循环
然后我们进入z=0的for循环
y如果大于等于cost[x][z]证明我们有钱买这个组合
1000>=cost[3][0]?
1000>=400?答案是是
我们更新我们的
dp[y] = fmax(dp[y], weight[x][z] + dp[y-cost[x][z]]);
dp[1000] = fmax(dp[1000], weight[3][0] + dp[1000 - cost[3][0])
| weight表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 1600 | 3600 | 3100 | 5100 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 1200 | 1200 | 1200 | 1200 |
| 4 | 1000 | 1000 | 1000 | 1000 |
dp[1000] = fmax(1600, 1200 + dp[1000 - 400])
dp[1000] = fmax(1600, 1200 + dp[600])
| dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | dp[6] | dp[7] | ... | dp[800] | ... | dp[1000] |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1600 | 1600 | 1600 |
dp[1000] = fmax(1600,1200) = 1600
所以我们的dp[1000]的值没变
接下来我们的z=1,2,3的情况和z=0一样
然后我们的y开始减少,当减少到790的时候,此时我们仍然可以买得起第四个物品(x=3)
我们的y=790,z=0时
790仍然>=400所以我们的
dp[y] = fmax(dp[y], weight[x][z] + dp[y-cost[x][z]])
dp[790] = fmax(dp[790], weight[3][0] + dp[790 -cost[3][0])
dp[790] = fmax(0, 1200 + dp[790 - 400])
dp[790] = fmax(0, 1200 + dp[390])
dp[790] = 1200
| dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | dp[6] | ... | dp[790] | dp[800] | ... | dp[1000] |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1200 | 1600 | 1600 | 1600 |
之后直到y=390之前,我们的dp值都被物品四刷新
| dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | ... | dp[400] | ... | dp[790] | dp[800] | ... | dp[1000] |
| 0 | 0 | 0 | 0 | 0 | 0 | 1200 | 1200 | 1200 | 1600 | 1600 | 1600 |
之后因为运算不够所以刷新不了满意度
然后我们进入第五个物品x=4
先判断是否是附件
if(cost[x][0] == 0) continue;
cost[4][0] 的值是500不是0我们进入y=1000
我们进入z=0
先判断是否有预算购买y >= cost[x][z]
1000 >= cost[4][0]
| cost表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 800 | 1200 | 1100 | 1500 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 400 | 400 | 400 | 400 |
| 4 | 500 | 500 | 500 | 500 |
1000 >= 500
发现预算足够,于是我们更新满意度
dp[y]=fmax(dp[y],weight[x][z]+dp[y-cost[x][z]])
dp[1000] = fmax(dp[1000],weight[4][0] + dp[1000 - cost[4][0])
| weight表-编号\主附件 | 0（表示是主件） | 1（表示第一个附件） | 2（表示第二个附件） | 3（表示第一个和第二个附件） |
| 0 | 1600 | 3600 | 3100 | 5100 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 1200 | 1200 | 1200 | 1200 |
| 4 | 1000 | 1000 | 1000 | 1000 |
dp[1000] = fmax(1600, 1000 + dp[1000 - 500])
dp[1000] = fmax(1600, 1000 + dp[500])
| dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | ... | dp[400] | ... | dp[500] | ... | dp[790] | dp[800] | ... | dp[1000] |
| 0 | 0 | 0 | 0 | 0 | 0 | 1200 | 1200 | 1200 | 1200 | 1200 | 1600 | 1600 | 1600 |
dp[1000] = fmax(1600, 1000 + 1200)
dp[1000] = fmax(1600, 2200)
dp[1000] = 2200
此时我们预算y=1000时的最大满意度被刷新
可以看到我们通过记录花费500元时可以购买到物品3的满意度为1200在我们的动态规划数组dp中,我们实现了对于花1000元时购买物品满意度的刷新
因为我们第五个物品的价格是500,购买它得到的满意度是1000,所以我们求我们剩下的钱1000 - 500能达到的最大满意度为1200,这两者相加大于之前我们话费1000元能达到的最大满意度1600,所以我们的dp[1000]更新为2200
之后因为我们的z没有附件所以z=0,1,2,3的情况是一样的
之后我们的y-=10,直到我们不能满足dp[y] < weight[x][z]+dp[y-cost[x][z]]
我们的dp都会刷新成2200
所以我们得到当y=900时
dp[900] = fmax(dp[900], weight[4][0] + dp[900 -cost[4][0])
dp[900] = fmax(1600, 1000 + dp[900 - 500])
dp[900] = fmax(1600, 1000 + dp[400])
dp[900] = fmax(1600, 2200)
dp[900] = 2200
| dp[0] | dp[1] | ... | dp[400] | ... | dp[790] | dp[800] | ... | dp[890] | dp[900] | ... | dp[1000] |
| 0 | 0 | 0 | 1200 | 1200 | 1200 | 1600 | 1600 | 1600 | 2200 | 2200 | 2200 |
当y-=10 y=890时
890虽然仍然大于500
但是此时我们已经不能刷新满意度了,因为我们的dp[390]为0
dp[890] = fmax(dp[890], weight[4][0] + dp[900 -cost[4][0])
dp[890] = fmax(1600, 1000 + 0)
dp[890] = 1600
这样直到y = 790的时候
dp[790] = fmax(dp[790], 1000)
dp[790] = fmax(1200,1000)
dp[790] = 1200
也无法刷新我们的满意度,
然后我们的y = 490时
因为490 < 500我们买不起物品五了,
然后x++ 此时我们x=5,跳出循环
这个时候我们的dp[y]就是我们计算出来的我们预算为y能够得到的最大满意度了
将结果输出就可以了
15:51-1:18:50
标签：主件,HJ16,物品,cost,附件,机试,购物单,dp,1000 From： https://blog.csdn.net/bingw0114/article/details/143303153