华为机试题16-购物单
此题比一般的0-1背包问题复杂一些,主要是多了附件的情况,而且要买附件的前提是已经买了主件,此处我们使用二维数组p存放物品的价格,二维数组v存放物品的价值(价格*重要度),其中第0列存放主件属性,第1列存放附件1的属性,第2列存放附件2的属性。
上述文字的操作就是为了将问题简化,最重要的是状态转移方程f[n][m]的编写,这里f[n][m]的含义表示:有n个主件,预算为m的情况下,能获得的最大满意度。将n转换成主件个数,有以下几种情况:
1、如果j<p[i][0],即如果预算j<第i个主件的价格,则f[i][j]=f[i-1][j],因为第i个主件买不起
2、如果j>=p[i][0],即如果预算j>=第i个主件的价格,则又要比较买了第i个主件和不买第i个主件的大小,取最大值
现在将附件加以考虑,如果买了第i个主件,在资金约束条件下,总共有4种情况:
2.1 仅买主件
2.2 主件+附件1
2.3 主件+附件2
2.4 主件+附件1+附件2
综合考虑以上五种情况,取其中的最大值赋给f[i][j]即可
以下为代码实现
#include <stdio.h>
#define N 60 /* N 表示可购买物品的个数, 题目描述不会超过60 */
#define M 32000 /* M 表示总钱数, 题目描述不会超过32000 */
int price[N][3];
int value[N][3];
int f[N][M]; /* 状态转移表达式,根据题意开辟最大的空间 */
static int max(int a, int b)
{
return (a > b ? a : b);
}
int main()
{
int m; /* m表示scanf格式化输入的总预算 */
int n; /* n表示scanf格式化输入的总物品个数 */
int i, j; /* 下标i, j用于遍历for循环 */
int p1; /* p1表示scanf格式化输入的物品价格 */
int w; /* w表示scanf格式化输入的物品重要度 */
int z; /* z表示scanf格式化输入的物品属性,物品是主件还是附件。如果 z=0 ,表示该物品为主件,如果 z>0 ,表示该物品为附件,z是所属主件的编号 */
int p[N][3]; /* p表示每个物品的价格,共3列,第0列表示主件的价格,第1列表示附件1的价格,第2列表示附件2的价格,下同 */
int v[N][3]; /* v表示每个物品的满意度,共3列,略 */
int temp[5]; /* 分别表示5种情况的满意度 */
scanf("%d%d", &m, &n);
for (i = 1; i <= n; i++) {
scanf("%d%d%d", &p1, &w, &z);
if (z == 0) { /* 该物品为主件 */
price[i][0] = p1; /* 第0列记录主件价格 */
value[i][0] = p1 * w; /* 第0列记录主件满意度 */
} else { /* 非主件 */
if (price[z][1] == 0) { /* 附件1未初始化,此物品成为附件1 */
price[z][1] = p1;
value[z][1] = p1 * w;
} else { /* 有附件1了,此物品成为附件2 */
price[z][2] = p1;
value[z][2] = p1 * w;
}
}
}
for (i = 1, j = 1; i <= n; i++) { /* 此次循环将所有主件挑出来重新排列,因为附件信息在上述循环中已经记录 */
if (price[i][0] != 0) { /* 全局变量初始化为0,不为0表示该物品是主件 */
p[j][0] = price[i][0];
p[j][1] = price[i][1];
p[j][2] = price[i][2];
v[j][0] = value[i][0];
v[j][1] = value[i][1];
v[j][2] = value[i][2];
j++;
}
}
n = j - 1; /* n重新赋值,表示所有主件的个数 */
for (i = 1; i <= n; i++) { /* 遍历n个主件 */
for (j = 1; j <= m; j++) { /* 遍历预算m */
memset(temp, 0, sizeof(temp));
temp[0] = f[i - 1][j]; /* temp[0]表示不买主件i,所以满意度值和f[i-1][j]保持一致 */
if(j >= p[i][0]) { /* 预算够买主件i,买它 */
temp[1] = f[i - 1][j - p[i][0]] + v[i][0];
}
if (j >= (p[i][0] + p[i][1])) {
temp[2] = f[i - 1][j - p[i][0] -p[i][1]] + v[i][0] + v[i][1];
}
if (j >= (p[i][0] + p[i][2])) {
temp[3] = f[i - 1][j - p[i][0] - p[i][2]] + v[i][0] + v[i][2];
}
if (j >= (p[i][0] + p[i][1] + p[i][2])) {
temp[4] = f[i - 1][j - p[i][0] - p[i][1] - p[i][2]] + v[i][0] + v[i][1] + v[i][2];
}
f[i][j] = max(temp[4], max(max(temp[0], temp[1]), max(temp[2], temp[3])));
}
}
printf("%d\n", f[n][m]);
return 0;
}