首页 > 代码库 > [HDU 3033] I love sneakers! (动态规划分组背包)
[HDU 3033] I love sneakers! (动态规划分组背包)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3033
题意：给你K种品牌，每种品牌有不同种鞋，现在每种品牌至少挑一款鞋，问获得的最大价值，如果不能每种品牌都挑到则输出Impossible
自己太弱了！！！！！这个题都想不出来！！！！！还要看题解！！！！！！
设计状态dp[i][j]代表从前i种品牌里花了不超过j元钱。
那么状态转移可以这样：
1.我只买第i种品牌的第k个。
2.我在第i种品牌里不光买第k个。
变成状态转移方程就是：
1. dp[i][j] = dp[i-1][j-p[i][k]]+v[i][k];
2. dp[i][j] = dp[i][j-p[i][k]]+v[i][k];
对于每组，是一个01背包问题。
两个取最大。
本人太弱了。。这种题还看题解- -
代码：
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <map> 6 #include <iterator> 7 #include <vector> 8 using namespace std; 9 typedef long long LL;10 11 int N,M,K;12 int p[11][111],v[11][111];13 int dp[11][11111];14 const int INF = 99999999;15 16 int main(){17 while(scanf("%d%d%d",&N,&M,&K)!=EOF){18 memset(p,0,sizeof(p));19 memset(v,0,sizeof(v));20 for(int i=1;i<=N;i++){21 int x,y,z;22 scanf("%d%d%d",&x,&y,&z);23 p[x][++p[x][0]] = y;24 v[x][++v[x][0]] = z;25 }26 for(int i=1;i<11;i++){27 for(int j=0;j<11111;j++){28 dp[i][j] = -INF;29 }30 }31 // dp[0][0] = 0;32 for(int i=1;i<=K;i++){33 for(int k=1;k<=p[i][0];k++){34 for(int j=M;j>=p[i][k];j--){35 dp[i][j] = max(dp[i][j],max(dp[i-1][j-p[i][k]]+v[i][k],dp[i][j-p[i][k]]+v[i][k]));36 }37 }38 }39 if(dp[K][M]<0) puts("Impossible");40 else printf("%d\n",dp[K][M]);41 }42 return 0;43 }
[HDU 3033] I love sneakers! (动态规划分组背包)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。