hdu3449 有依赖的背包问题

发布时间：2020-12-13 22:45:35 所属栏目：百科来源：网络整理

导读：题意：给你一些物品，每个物品有自己的价值和花费，每个物品都对应一个箱子，每个箱子有价钱，买这个物品必须买相应的箱子，给你一个价钱，问最多可以获得多少价值提示：多个物品可能同时对应着一个箱子。思路：典型的有依赖的背包，每个箱子是“主件”

题意：
给你一些物品，每个物品有自己的价值和花费，每个物品都对应一个箱子，每个箱子有价钱，买这个物品必须买相应的箱子，给你一个价钱，问最多可以获得多少价值
<提示：多个物品可能同时对应着一个箱子>。

思路：

典型的有依赖的背包，每个箱子是“主件” 每个箱子所对应的物品是他的“附件”，有依赖的背包的过程就是把没一组主件和附件的集合中附件跑一遍01背包，然后把主件强加到跑完后的数组里，然后再在虽有的集合中选择最优的dp[i]的值，这样更新到最后就行了，这样更新跑附件之间的01背包后强加主件是对应着题意的必须有盒子，而集合和集合之间的更新是对应着可以再多可集合中选择最优。

#include<stdio.h>
#include<string.h>

#define N 1100000
 int dp[N],tmp[N]; int maxx(int x,int y) { return x > y ? x : y; } int main () { int n,m,i,j,k,c,w,p,nn; while(~scanf("%d %d",&n,&m)) {
      memset(dp,0,sizeof(dp));
      memset(tmp,sizeof(tmp)); for(i = 1 ;i <= n ;i ++) {
         memcpy(tmp,dp,sizeof(dp));
         scanf("%d %d",&p,&nn); for(j = 1 ;j <= nn ;j ++) {
            scanf("%d %d",&w,&c); for(k = m ;k >= w ;k --)
            tmp[k] = maxx(tmp[k],tmp[k-w] + c); } for(j = p ;j <= m ;j ++)
         dp[j] = maxx(dp[j],tmp[j-p]); }  
      printf("%dn",dp[m]); } return 0; }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!