金明的预算方案--分组背包

柔情只为你懂 2021-12-20 15:55 198阅读 0赞

【2006提高】金明的预算方案

**Description**

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：  
　　主件 附件  
　　电脑 打印机，扫描仪  
　　书柜 图书  
　　书桌 台灯，文具  
　　工作椅 无  
　　如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。  
  
　　设第j件物品的价格为v\[j\]，重要度为w\[j\]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v\[j1\]\*w\[j1\]+v\[j2\]\*w\[j2\]+ …+v\[jk\]\*w\[jk\]。（其中\*为乘号）请你帮助金明设计一个满足要求的购物单。

**Input**

输入文件的第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是所属主件的编号）

**Output**

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值  
（<200000）。

**Sample Input**

1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

**Sample Output**

2200

**Source**

xinyue

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 代码

1 \#include < stdio.h >   
  2 \#include < stdlib.h >   
  3 \#include < string .h >   
  4  int  a\[ 61 \]\[ 3 \],w\[ 61 \],v\[ 61 \],f\[ 32000 \],n,m;  
  5 FILE  \* in , \* out ;  
  6   
  7  int  main()\{  
  8  int  i,j,x,y,z,max ;  
  9  memset(a, 0 , sizeof (a));  
 10  memset(f, 0 , sizeof (f));  
 11  in = fopen( " budget1.in " , " r " );  
 12  out = fopen( " budget.out " , " w " );  
 13  fscanf( in , " %d%d " , & m, & n);  
 14  for (i = 1 ;i <= n;i \++ )  
 15  \{  
 16  fscanf( in , " %d%d%d " , & w\[i\], & x, & y);  
 17  v\[i\] = w\[i\] \* x;  
 18  if (y == 0 )a\[i\]\[ 0 \] = w\[i\];  
 19  else   
 20  \{  
 21  if (a\[y\]\[ 1 \] == 0 )a\[y\]\[ 1 \] = i;  
 22  else  a\[y\]\[ 2 \] = i;  
 23  \}  
 24  \}  
 25   
 26  for (i = 1 ;i <= n;i \++ )  
 27  if (a\[i\]\[ 0 \])  
 28  for (j = m;j >= 1 ;j \-- )  
 29  \{  
 30  max = f\[j\];  
 31  if (j \- a\[i\]\[ 0 \] >= 0 )  
 32  if (max < f\[j \- a\[i\]\[ 0 \]\] \+ v\[i\])  
 33  max = f\[j \- a\[i\]\[ 0 \]\] \+ v\[i\];  
 34   
 35  if (a\[i\]\[ 1 \] && (j \- a\[i\]\[ 0 \] \- w\[a\[i\]\[ 1 \]\] >= 0 ))  
 36  if (max < f\[j \- a\[i\]\[ 0 \] \- w\[a\[i\]\[ 1 \]\]\] \+ v\[i\] \+ v\[a\[i\]\[ 1 \]\])  
 37  max = f\[j \- a\[i\]\[ 0 \] \- w\[a\[i\]\[ 1 \]\]\] \+ v\[i\] \+ v\[a\[i\]\[ 1 \]\];  
 38   
 39  if (a\[i\]\[ 2 \] && (j \- a\[i\]\[ 0 \] \- w\[a\[i\]\[ 2 \]\] >= 0 ))  
 40  if (max < f\[j \- a\[i\]\[ 0 \] \- w\[a\[i\]\[ 2 \]\]\] \+ v\[i\] \+ v\[a\[i\]\[ 2 \]\])  
 41  max = f\[j \- a\[i\]\[ 0 \] \- w\[a\[i\]\[ 2 \]\]\] \+ v\[i\] \+ v\[a\[i\]\[ 2 \]\];  
 42   
 43  if (a\[i\]\[ 1 \] && a\[i\]\[ 2 \] && (j \- a\[i\]\[ 0 \] \- w\[a\[i\]\[ 1 \]\] \- w\[a\[i\]\[ 2 \]\] >= 0 ))  
 44  if (max < f\[j \- a\[i\]\[ 0 \] \- w\[a\[i\]\[ 2 \]\] \- w\[a\[i\]\[ 1 \]\]\] \+ v\[i\] \+ v\[a\[i\]\[ 2 \]\] \+ v\[a\[i\]\[ 1 \]\])  
 45  max = f\[j \- a\[i\]\[ 0 \] \- w\[a\[i\]\[ 2 \]\] \- w\[a\[i\]\[ 1 \]\]\] \+ v\[i\] \+ v\[a\[i\]\[ 2 \]\] \+ v\[a\[i\]\[ 1 \]\];  
 46  f\[j\] = max;  
 47  \}  
 48  printf( " %d\\n " ,f\[m\]);  
 49  fprintf( out , " %d\\n " ,f\[m\]);  
 50  system( " pause " );  
 51  fclose( in );  
 52  fclose( out );  
 53  return  0 ;  
 54  \}

f\[j\]任然与0-1背包中代表的是一样的。这个问题主要是把主件与附件捆绑，每次找出  
只选主件、选主件与附件1、选主件与附件2、选主件与附件1和2、都不选  
5种情况中最大的一个，赋值给f\[j\].需要有一点注意：第二重循环需要从后向前搜索。

转载于:https://www.cnblogs.com/aiyite826/archive/2010/07/23/1783841.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/c91d719930b84ee48f0c3f462ca16428.png