首页 > 代码库 > HDU 3449 有依赖的01背包
HDU 3449 有依赖的01背包
给出n个盒子,和总钱数w
对于n个盒子,首先买盒子需要花费m,然后可以买盒子中的物品,每个物品分别有其花费a[i].w和价值a[i].v
典型的有依赖的01背包
mark存储前i-1个盒子的dp值
然后对于当前盒子,先不考虑其盒子的花费进行01背包
然后对于mark数组的得到的每个新值mark[i},去更新dp[i+a[i].m];
#include "stdio.h" #include "string.h" struct node { int n,m; int w[11],v[11]; } a[51]; int dp[100010],mark[100010]; int Max(int a,int b) { if (a<b) return b; else return a; } int main() { int n,w,i,j,k,ans; while (scanf("%d%d",&n,&w)!=EOF) { for (i=1; i<=n; i++) { scanf("%d%d",&a[i].m,&a[i].n); for (j=1; j<=a[i].n; j++) scanf("%d%d",&a[i].w[j],&a[i].v[j]); } memset(dp,0,sizeof(dp)); for (i=1; i<=n; i++) { for (k=0; k<=w; k++) mark[k]=dp[k]; for (j=1; j<=a[i].n; j++) for (k=w; k>=a[i].w[j]; k--) { if (mark[k-a[i].w[j]] + a[i].v[j] >mark[k]) mark[k]=mark[k-a[i].w[j]]+a[i].v[j]; } for (k=0; k+a[i].m<=w; k++) dp[k+a[i].m]=Max(dp[k+a[i].m],mark[k]); } ans=0; for (i=0; i<=w; i++) ans=Max(ans,dp[i]); printf("%d\n",ans); } return 0; }
HDU 3449 有依赖的01背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。