物件捆绑背包问题：给定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
     
      #include
      
       #include
       
        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
        
         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
         
          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);        }    }}