首页 > 代码库 > [HDU 3033] I love sneakers! (动态规划分组背包)

[HDU 3033] I love sneakers! (动态规划分组背包)

2024-07-29 11:52:22   229人阅读

题目链接：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! (动态规划分组背包)


联系
我们