hdu3033 I love sneakers! 分组背包变形

分组背包要求每一组里面只能选一个，这个题目要求每一组里面至少选一个物品。

dp[i, j] 表示前 i 组里面在每组至少放进一个物品的情况下，当花费 j 的时候，所得到的的最大价值。这个状态可以由三个状态转移过来：

dp[i-1, v-a[i,j].b] 表示第 i 组没有放过，将要放进第 i 组里面的第 j 个物品
dp[i, v-a[i,j].b] 表示第 i 组已经放过了，将要放进第 i 组里面的第 j 个物品
dp[i, j] 表示第 i 中已经放过了，不放第 i 组里面的第 j 个物品

a[i, j].b表示第 i 组第 j 个物品的花费，v表示背包容量。

初始化：

如果一种物品都不放，那么对应的所有的背包容量都是0，也就是：dp[0, 0~M] = 0；

其他的情况，都初始化成-INF。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <cctype>
 7 #include <algorithm>
 8 #include <queue>
 9 #include <deque>
10 #include <queue>
11 #include <list>
12 #include <map>
13 #include <set>
14 #include <vector>
15 #include <utility>
16 #include <functional>
17 #include <fstream>
18 #include <iomanip>
19 #include <sstream>
20 #include <numeric>
21 #include <cassert>
22 #include <ctime>
23 #include <iterator>
24 const int INF = 0x3f3f3f3f;
25 const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
26 using namespace std;
27 typedef struct node
28 {
29     int b,v;
30 }node;
31 vector<node> a[11];
32 int dp[11][10009];
33 int main(void)
34 {
35     #ifndef ONLINE_JUDGE
36     freopen("in.txt","r",stdin);
37     #endif // ONLINE_JUDGE
38     int n, V, k;
39     while (~scanf("%d%d%d",&n,&V,&k))
40     {
41         for (int i=0;i<k;++i) a[i+1].clear();
42         int id; node t;
43         for (int i=0;i<n;++i)
44         {
45             scanf("%d",&id); scanf("%d%d",&t.b,&t.v); a[id].push_back(t);
46         }
47         bool flag=false;
48         for (int i=0;i<k;++i) if(a[i+1].size()==0) {printf("Impossible
"); flag=true; break; }
49         if(flag) {continue;}
50         memset(dp,-INF,sizeof(dp));
51         for (int i=0;i<=V;++i) dp[0][i]=0;
52         for (int i=1;i<=k;++i)
53         {
54             for (int j=0;j<a[i].size();++j)
55             {
56                 for (int v=V; v>=a[i][j].b;--v)
57                 {
58                     if(dp[i][v-a[i][j].b]!=-INF) dp[i][v]=max(dp[i][v],dp[i][v-a[i][j].b]+a[i][j].v);
59                     if(dp[i-1][v-a[i][j].b]!=INF) dp[i][v]=max(dp[i][v],dp[i-1][v-a[i][j].b]+a[i][j].v);
60                 }
61             }
62         }
63         if(dp[k][V]==-INF) printf("Impossible
");
64         else printf("%d
",dp[k][V]);
65     }
66     return 0;
67 }

当然不是我自己想出来的……

参考：

http://www.cnblogs.com/zhourongqing/archive/2012/08/21/2649972.html

http://www.docin.com/p-374335925.html

http://www.cnblogs.com/nanke/archive/2011/11/24/2261695.html