HDU3033I love sneakers!(分组背包)

http://acm.hdu.edu.cn/showproblem.php?pid=3033

本题的意思就是说现在有n种牌子的鞋子，每种品牌有一些不同的鞋，每双鞋子都有一个特定的权值，现在要求每种品牌的鞋子都至少收集一双，有一定量的钱，问获得的最大的权值是多少。

这个题与普通的分组背包不同就在于每一组都至少选一个，（正好这个难道我了＝＝）

网上找了解题报告，解题方法很巧妙，就是先将每一个DP值初始化为一个值，比如－1，表示所有的状态都不合法

那么转移方程就是

                    if(DP[i][k-cost[i][j]] != -)

                        DP[i][k] = max(DP[i][k], DP[i][k-cost[i][j]]+val[i][j]);

                    if(DP[i-][k-cost[i][j]] != -)

                        DP[i][k] = max(DP[i][k], DP[i-][k-cost[i][j]]+val[i][j]);

这样一来，如果要得到一个DP值，就必须从一个合法的状态得到，首先，如果DP[i][k-cost[i][j]]！=-1,那么说明这一层已经存放了物品，否则就是没有放那么就必须从上一层的状态转移得到。

得解。

见代码：

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define MAX(a,b) (a > b ? a : b)

 #define MIN(a,b) (a < b ? a : b)

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 typedef long long LL;

 const double eps = 1e-;

 const int MAXN = ;

 const int MAXM = ;

 int num[],cost[][], val[][];

 int DP[][], sum;

 int N, M, K;

 void init()

 {

     mem0(DP); mem0(cost);mem0(val);mem0(num);

     num[] = ;

 }

 void ReadData()

 {

     int a, b, c;

     for(int i=;i<N;i++)

     {

         scanf("%d%d%d", &a, &b, &c);

         cost[a][num[a]] = b;

         val[a][num[a]] = c;

         num[a]++;

     }

 }

 int main()

 {

     while(~scanf("%d %d %d", &N, &M, &K))

     {

         init();

         ReadData();

         for(int i=;i<=K;i++)

         {

             for(int j=;j<=M;j++)

             {

                 DP[i][j] = i==?:-;

             }

         }

         for(int i=;i<=K;i++)

         {

             for(int j=;j<num[i];j++)

             {

                 for(int k=M;k>=cost[i][j];k--)

                 {

                     if(DP[i][k-cost[i][j]] != -)

                         DP[i][k] = max(DP[i][k], DP[i][k-cost[i][j]]+val[i][j]);

                     if(DP[i-][k-cost[i][j]] != -)

                         DP[i][k] = max(DP[i][k], DP[i-][k-cost[i][j]]+val[i][j]);

                 }

             }

         }

         if(DP[K][M]<)printf("Impossible\n");

         else printf("%d\n",DP[K][M]);

     }

     return ;

 }

巴特西

HDU3033I love sneakers!(分组背包)

最新文章

热门文章