题目描述
王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：
v[j 1 ]w[j 1 ]+v[j 2 ]w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 为乘号）
请你帮助王强设计一个满足要求的购物单。
2.输入输出
输入描述:
输入的第 1 行，为两个正整数，用一个空格隔开：N m
（其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
输出描述:
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。
3.解题思路
此题目可先化简为分组背包问题，再求解.
4.源码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 有条件分组背包问题(购物单问题)
* p = 5
* h = (800, 2, 0), (400, 5, 1), (300, 5, 1),
* (400, 3, 0), (500, 2, 0)
* w = (800, 1200, 1100, 1500), ( 400), ( 500)
* v = (1600, 3600, 3100, 5100), (1200), (1000)
* c = 1000
*/
int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
/*int w[61][11] = {{0, 0}, {4, 80, 120, 110, 150}, {1, 40}, {1, 50}};
int v[61][11] = {{0, 0}, {4, 1600, 3600, 3100, 5100}, {1, 1200}, {1, 1000}};*/
int w[61][11];
int v[61][11];
int u[61][3201];
int m[61][3201];
int h[3][61];
int b[61][51];
int d[61];
int g[61];
int x[61];
int t[5];
int r[61][10][4];
int n = 3;
int s = 0;
int c = 100;
int z = 0;
int l;
int i, j, k;
j = 1;
memset(m, 0x00, sizeof(m));
memset(u, 0x00, sizeof(u));
memset(r, 0x00, sizeof(r));
memset(w, 0x00, sizeof(w));
memset(v, 0x00, sizeof(v));
scanf("%d %d", &c, &s);
c /= 10;
for(i=1; i<=s; i++)
{
scanf("%d %d %d", &h[0][i], &h[1][i], &h[2][i]);
if(!h[2][i])
{
b[j][0] = i; /*第j个组的主件的行数*/
d[i] = j; /*第i行属于哪个组*/
j++; /*组数量+1*/
}
else
{
t[0] = h[2][i]; /*附件属于哪一行的主件*/
t[1] = d[t[0]]; /*主件属于哪一个组*/
g[t[1]]++; /*组元素加一*/
t[2] = g[t[1]]; /*组元素编号*/
b[t[1]][t[2]] = i; /*组中的附件编号所属行数*/
}
}
l = j - 1; /*组个数*/
/*(for(i=1; i<=l; i++)
{
for(j=0; j<=g[i]; j++)
{
printf("b[%d][%d]=%d ", i, j, b[i][j]);
}
printf("\n");
}*/
for(i=1; i<=l; i++)
{
/*无附件情况*/
t[0] = 1;
t[1] = b[i][0]; /*组中的主件所属行数*/
w[i][t[0]] = h[0][t[1]] / 10; /*主件价格*/
v[i][t[0]] = h[1][t[1]] * h[0][t[1]]; /*主件目标权重*/
r[i][t[0]][0] = 1; /*第i组第几种排列方式*/
t[0]++;
/*一种附件情况*/
for(j=1; j<=g[i]; j++)
{
t[1] = b[i][0];
t[2] = b[i][j];
r[i][t[0]][0] = 1;
r[i][t[0]][j] = t[1];
w[i][t[0]] = (h[0][t[1]] + h[0][t[2]]) / 10;
v[i][t[0]] = h[1][t[1]] * h[0][t[1]] + h[1][t[2]] * h[0][t[2]];
t[0]++;
}
/*两种附件情况*/
for(j=1; j<=g[i]; j++)
{
for(k=j+1; k<=g[i]; k++)
{
t[1] = b[i][0];
t[2] = b[i][j];
t[3] = b[i][k];
r[i][t[0]][0] = 1;
r[i][t[0]][j] = 1;
r[i][t[0]][k] = 1;
w[i][t[0]] = (h[0][t[1]] + h[0][t[2]] + h[0][t[3]]) / 10;
v[i][t[0]] = h[1][t[1]] * h[0][t[1]] + h[1][t[2]] * h[0][t[2]] + h[1][t[3]] * h[0][t[3]];
t[0]++;
}
}
w[i][0] = t[0] - 1;
v[i][0] = w[i][0];
}
/*for(i=1; i<=l; i++)
{
for(k=1; k<=w[i][0]; k++)
{
printf("w[%d][%d]=%d\n", i, k, w[i][k]);
}
}*/
n = l;
for(i=1; i<=n; i++)
{
for(j=1; j<=c; j++)
{
z = m[i-1][j];
for(k=1; k<=w[i][0]; k++)
{
if(j >= w[i][k])
{
m[i][j] = max(z, m[i-1][j-w[i][k]]+v[i][k]);
if(m[i][j] > z)
{
u[i][j] = k;
z = m[i][j];
}
}
else
{
m[i][j] = z;
}
}
}
}
/*for(i=1; i<=n; i++)
{
for(j=1; j<=c; j++)
{
printf("%d\t", m[i][j]);
}
printf("\n");
}*/
printf("%d\n", m[n][c]);
for(i=n; i>=1; i--)
{
if(u[i][c])
{
x[i] = u[i][c];
c -= w[i][x[i]];
}
else
{
x[i] = 0;
}
}
/*for(i=1; i<=n; i++)
{
printf("%d\t", x[i]);
}
printf("\n");*/
return 0;
}
5.编译源码
$ gcc -o example examle.c -std=c89
6.运行及其结果
$ ./example
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
2200
网友评论