物件捆绑 背包问题 动态规划 求解解析

访客 阅读:380 2020-10-19 15:34:59 评论:0

  物件捆绑背包问题:给定N元钱,要购买一些器件。器件有主件和附件之分,也即主件可以单独购买,然而购买附件必须购买对应的主件。下表就是一些主件与附件的例子

主件 附件
电脑      打印机、扫描仪
书柜 图书
书桌          台灯
工作椅

     把每件物品规定一个重要度,分为5等:用整数1~5表示,第5等最重要。在花费不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大设第j件物品的价格为v[j],重要度为p[j],共选中了k件物品,编号依次为j1j2,……,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  qv:物品价格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); 
        } 
    } 
}
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
KIKK导航

KIKK导航

关注我们