本文主要是介绍HDU 2844 Coins（多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
以前做题目光仅仅局限于 0 1 背包 和 完全背包了。
出来一个 个数确定的背包就不会了。 看了网上的题解。 原来是多重背包。 也就是说 用完全背包和 0 1背包混合求解的题目。
应该是。 对于 vi*a【i】 >= m 那么就相当于一个完全背包。 因为数量可以超过 最大限制。那么就可以当做无限个使用。
其他的 就需要二进制来优化了。 比如 13 个 2的话。 就用二进制来表示 1 个 2 2个 2 4 个 2 6 个 2 因为这样就可以 把 1 2 3 4 5 6 。。。。这些所有的情况都可以表示出来
比如 5 个 2 就是 1个2 + 4个2 6 就是 2个 2+ 4个2 11 就是 1 + 4 + 6. 所以 当做 0 1 背包来说的话。 最大表示 只能是 13. 并且可以表示所有的情况。
所以就满足题意。 就把 原来的 m*（∑a【i】） 变成了 m* （∑log（a【i】））。 优化了很多。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <fstream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cmath>
#include <iomanip>
#include <cmath>
typedef long long LL;
typedef unsigned long long LLU;
const double PI=acos(-1.0);
using namespace std;
#define MAXN 100+10
#define INF 1 << 30
struct Coin{int v;int num;
};
int main (){int n,m;while(scanf("%d%d",&n,&m) != EOF){if(n == 0 && m == 0)break;Coin s[MAXN];int f[100000+10] = {0};f[0] = 1;for(int i = 1; i <= n; i++)scanf("%d",&s[i].v);for(int i = 1; i <= n; i++)scanf("%d",&s[i].num);for(int i = 1; i <= n; i++){if(s[i].num*s[i].v >= m){for(int j = s[i].v; j <= m; j++)f[j] = f[j]|f[j-s[i].v];}else{int k = s[i].num/2;int j;for(j = 1; j <= k; j=(j<<1)){for(int x = m; x >= s[i].v*j; x--){f[x] = f[x]|f[x-s[i].v*j];}}k = s[i].num+1-j;for(int x = m; x >= s[i].v*k; x--)f[x] = f[x]|f[x-s[i].v*k];}}int co = 0;for(int i = 1; i <= m; i++)co += f[i];printf("%d\n",co);}return 0;
}
这篇关于HDU 2844 Coins（多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
