HDU 2191 悼念512汶川大地震遇难同胞—

HDU 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

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

题目是多重背包的题目,但是我们可以写成是0/1背包的格式。

0/1背包的代码：

View Code

 1 #include <iostream>
 2 #define maxn 101
 3 using namespace std;
 4 int ans[maxn], v[maxn], w[maxn], num[maxn];
 5 int main()
 6 {
 7     int i, j, l, n, m, t;
 8     cin >> t;
 9     while(t--)
10     {
11         cin >> m >> n;
12         for(i = 0; i < n; i++)
13           cin >> v[i] >> w[i] >> num[i];
14         for(i = 0; i <= m; i++)
15           ans[i] = 0;
16         for(i = 0; i < n; i++)
17          for(j = 0; j < num[i]; j++)
18           for(l = m; l >= v[i]; l--)
19           if(ans[l-v[i]]+w[i] > ans[l])
20             ans[l] = ans[l-v[i]]+w[i];
21         cout << ans[m] << endl;       
22     }
23     return 0;
24 }

完全背包的代码:

View Code

 1 #include <iostream>
 2 #define maxn 1001
 3 using namespace std;
 4 struct things
 5 {
 6     int cost, weight, amount;
 7 };
 8 things th[maxn];
 9 int ans[maxn], n, m;
10 void zero_one_pack(int cost, int weight)
11 {
12     int j;
13     for(j = m; j >= cost; j--)
14     if(ans[j] < ans[j-cost]+weight)
15      ans[j] = ans[j-cost]+weight;
16 }
17 void complete_pack(int cost, int weight)
18 {
19     int i, j;
20     for(j = 0; j <= m; j++)
21     if(j >= cost &&ans[j] < ans[j-cost]+weight)
22      ans[j] = ans[j-cost]+weight;
23 }
24 void mulity_pack(things now)
25 {
26     int i;
27     if(now.cost * now.amount >= m)
28     {
29         complete_pack(now.cost,now.weight);
30     }
31     else
32     {
33         for(i = 1; i < now.amount;)
34         {
35             zero_one_pack(i*now.cost, i*now.weight);
36             now.amount -= i;
37             i *= 2;
38         }
39         zero_one_pack(now.amount*now.cost,now.amount*now.weight);
40     }
41 }
42 int main()
43 {
44     int t, i, j;
45     cin >> t;
46     while(t--)
47     {
48          cin >> m >> n;
49         for(i = 0; i < n; i++)
50          cin >> th[i].cost >> th[i].weight >> th[i].amount;
51         for(i = 0; i <= m; i++)
52          ans[i] = 0;
53         for(i = 0; i < n; i++)
54         mulity_pack(th[i]);
55         cout << ans[m] << endl;
56     }
57     return 0;
58 }

对应的是背包九讲中的伪代码写的。

MULTIPLE_PACK(cost,weight,amount)

if cost * amount >= V

then COMPLETE_PACK(cost,weight)

return

int k ←1 while k < amount

ZERO_ONE_PACK(k * cost, k * weight)

amount ← amount - k

k ← k * 2

ZERO_ONE_PACK(amount * cost, amount * weight)

刚看到的时候，自己还没反应过来....

1.当处理到第 i 个物品时,可以得到物品的 cost,weight,amount

2.如果第 i 个物品的 cost * amount >= V, 说明可以全部选择第 i 个物品来装满 V 的花费

3. 将第 i 个物品当做是完全背包中的一个来处理

4.如果第 i 个物品不满足 2 的条件, 那么就将第 i 个物品则相当于是进行0/1背包中的一个物品来处理

5. 将第 i 个物品分成几份,具体的分发就是 K 的变化, 将设分成了m 个数字,则这m个数字可以通过组合得出

所有的 1--amount 中的数字。二进制思想体现在这里。然后对这 m 份物品进行0/1背包的处理。

6.此时的 amount 也是这 m 个数字中的, 也应该进行计算。

这样就讲所有的都处理完了.....\(^o^)/~

话说网上搜了挺多的多重背包的代码，但是都是背包九讲的COPY.....

自己总算看懂......O(∩_∩)O哈哈~