首页 > 代码库 > hdu 3449 Consumer (依赖01背包)
hdu 3449 Consumer (依赖01背包)
题目:
链接:点击打开链接
题意:
思路:
dp[i][j]表示前i个箱子装j钱的材料可以得到的最大价值。
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define MAXN 100010 int dp[55][MAXN]; int main() { //freopen("input.txt","r",stdin); int n,v; int pi,mi; int c,w; while(scanf("%d%d",&n,&v) != EOF) { memset(dp,0,sizeof(dp)); for(int i=1; i<=n; i++) { scanf("%d%d",&pi,&mi); for(int j=0; j<=pi; j++) dp[i][j] = -1; for(int j=v; j>=pi; j--)//依赖 dp[i][j] = dp[i-1][j-pi]; for(int j=0; j<mi; j++)//01背包 { scanf("%d%d",&c,&w); for(int k=v; k>=c; k--) { if(dp[i][k-c] != -1) dp[i][k] = max(dp[i][k],dp[i][k-c]+w); } } for(int j=v; j>=0; j--)//........... dp[i][j] = max(dp[i][j],dp[i-1][j]); } printf("%d\n",dp[n][v]); } return 0; }
hdu 3449 Consumer (依赖01背包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。