hdu 3449 Consumer （依赖01背包）

本文主要是介绍hdu 3449 Consumer （依赖01背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

        链接：点击打开链接

题意：

思路：

        dp[i][j]表示前i个箱子装j钱的材料能够得到的最大价值。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 100010int 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背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---