首页 > 代码库 > hdoj 2191 悼念512。。 【多重背包】+【二进制分解】

hdoj 2191 悼念512。。 【多重背包】+【二进制分解】

2024-07-15 16:39:21   219人阅读

话说题目真长。。。

题意： 中文题，你懂得。。

策略：多重背包问题。多重背包转换成 01 背包问题就是多了个初始化，把它的件数C 用2的次幂分解成若干个件数的集合，这里面数字可以组合成任意小于等于C的件数，而且不会重复，之所以叫二进制分解，是因为这样分解可

以用数字的二进制形式来解释

    比如：7的二进制 7 = 111 它可以分解成 001 010 100 这三个数可以
组合成任意小于等于7 的数，而且每种组合都会得到不同的数。
    15 = 1111 可分解成 0001  0010  0100  1000 四个数字
    如果13 = 1101 则分解为 0001 0010 0100 0110 前三个数字可以组合成
7以内任意一个数，加上 0110 = 6 可以组合成任意一个大于6 小于13
 的数，虽然有重复但总是能把 13 以内所有的数都考虑到了，基于这种
思想（二进制思想）去把多件物品转换为，多种一件物品，就可用01 背包求解了。
题目链接：点击打开链接
代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
int dp[555], w[555], v[555]; //w是质量，v是要花费的钱
int main()
{
	int t, n, m, p, h, c, cou;
	scanf("%d", &t);
	while(t --){
		scanf("%d%d", &n, &m);
		memset(dp, 0, sizeof(dp));
		cou = 0;
		int i, j;
		while(m --){
			scanf("%d%d%d", &p, &h, &c);
			/*for(i =1; i <= c; i += (int)pow(2.0, i)){  //用pow总是wa，查了一下，pow返回的不是int型，是double型，虽然测试数据能过，但是可能有些取整的时候就错了。 于是就直接用一个整数来判断了
				v[cou] = i*p;
				w[cou++] = i*h;
				c-=i;
			}*/
			int l = 1;
			while(c >= l){
				v[cou] = l*p;
				w[cou++] = l*h;
				c-=l;
				l<<=1;
			}
			if(c){
				v[cou] = c*p;
				w[cou++] = c*h;
			}
		}
		for(i = 0; i < cou; i ++){
			for(j = n; j >= v[i]; j --){
				if(dp[j] < dp[j-v[i]]+w[i]) 
					dp[j] = dp[j-v[i]]+w[i];
			}
		}
		printf("%d\n", dp[n]);
	}
	return 0;
}


联系
我们