物件捆绑背包问题：给定N元钱，要购买一些器件。器件有主件和附件之分，也即主件可以单独购买，然而购买附件必须购买对应的主件。下表就是一些主件与附件的例子：
| 主件 | 附件 |
| 电脑 | 打印机、扫描仪 |
| 书柜 | 图书 |
| 书桌 | 台灯 |
| 工作椅 | 无 |
把每件物品规定一个重要度，分为5等：用整数1~5表示，第5等最重要。在花费不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为p[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*p[j1]+v[j2]*p[j2]+ …+v[jk]*p[jk]。
输入
第1行，为两个正整数，用一个空格隔开：N m
从第2行到第m+1行中，第j行给出了编号为j-1的物品基本数据，每行有3个非负整数： v p q（v:物品价格，p:物品重要度，q:主件还是附件。q=0为主件；q>0为附件，q是所属主件的编号）
输出
输出为不超过总钱数的物品的价格与其重要度乘积的总和的最大值。
动态规划求解：
1)思路：同一般的背包问题不同的是，在购买附件的同时必须要购买相应的主件。我们需要对主，附件做捆绑。每一种捆绑结果作为一种购买方式，之后同一般的背包问题
例如：主件A，有附件B、附件C，则由数理统计的知识可知有4中购买方式，即（A，A+B，A+C，A+B+C）。
附件个数为n-1时的购买方式个数为：
2)主附件捆绑的数据结构选择：
因为一件附件只有一个主件，为了捆绑的方便性，可以采用链表的形式。主件为头结点，拉链为附件节点。如下所示：
3)问题求解
#include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct node { int price; ///价格 int priority; ///重要程度 struct node *next; }Node; typedef struct ///拉链数据结构 { Node num[60]; }List; int dp[360][32001]; int pos; ///用于标记数量 int n,m; ///总钱数和物品数 void input(List*); ///物件情况输入，并构造主附件捆绑的数据结构（拉链法） void preDP(List*); ///进行主附件的捆绑 void exeDP(int,int); ///执行动态规划 int main() { List list; while(scanf("%d %d",&n,&m)!=EOF) { input(&list); preDP(&list); printf("%d\n",dp[m][n]); } return 0; } void input(List* list) { int i; int v,p,q; ///分别代表价格，重要程度，以及主件的编号 Node *tmp; for(i=0;i<m;i++) { scanf("%d %d %d",&v,&p,&q); if(q==0) ///主件 { list->num[pos].price=v; list->num[pos].priority=p; list->num[pos].next=NULL; pos++; } else ///附件 { tmp=(Node*)malloc(sizeof(Node)); tmp->price=v; tmp->priority=p; tmp->next=list->num[q-1].next; ///使用头叉拉链法 list->num[q-1].next=tmp; } } } void preDP(List *list) { int i; int sumv,sumvp; Node *p=NULL,*tmp=NULL; m=-1; ///捆绑物品个数计数，从0开始。 for(i=0;i<pos;i++) ///对每个主件开始的链 { sumv=list->num[i].price; ///只包括主件 sumvp=list->num[i].price*list->num[i].priority; m++; exeDP(sumv,sumvp); p=list->num[i].next; while(p!=NULL) ///包括主件+附件的情况 { ///每次都要带主件 sumv=list->num[i].price; sumvp=list->num[i].price*list->num[i].priority; tmp=p; while(tmp!=NULL) { sumv=sumv+tmp->price; sumvp=sumvp+tmp->price*tmp->priority; m++; exeDP(sumv,sumvp); tmp=tmp->next; } tmp=p; p=p->next; free(tmp); } } } void exeDP(int sumv,int sumvp) { int i; for(i=0;i<=n;i++) { if(m==0) { if(sumv>i) dp[0][i]=0; else dp[0][i]=sumvp; } else { if(sumv>i) dp[m][i]=dp[m-1][i]; else dp[m][i]=dp[m-1][i]>(dp[m-1][i-sumv]+sumvp)? dp[m-1][i]:(dp[m-1][i-sumv]+sumvp); } } }
