HDOJ 1059 Dividing (多重背包例题)

问题很容易转化为多重背包问题。刚学背包（。。。）用它练练手。

多重背包的特殊性在于物品可以取多次。

首先利用二进制表示数的特点，可以把每个物品的个数由 n 降为 log n 。

然后就是01背包了。

方程：dp[i][v] = max(dp[i-1][v], dp[i-1][v-c[i]] + w[i])

试了下01背包的空间复杂度优化。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200000, inf = 0x3f3f3f3f;
int a[6], c[maxn], w[maxn], dp[maxn];
int sum;
int read()
{
sum = 0;
for(int i = 1; i <= 6; i++) {
scanf("%d", &a[i]);
sum += i * a[i];
}
return sum;
}
int main()
{
for(int ca = 1; read() > 0;) {
int cnt = 0, v = sum / 2;
bool ok = 0;
if(sum&1)
goto flag;
for(int i = 1; i <= 6; i++) {
int temp = a[i], k = 1;
while(temp >= k) {
cnt++;
w[cnt] = k;
c[cnt] = i * k;
temp -= k;
k <<= 1;
}
if(temp != 0) {
cnt++;
w[cnt] = temp;
c[cnt] = i * temp;
}
}
dp[0] = 0;
for(int i = 1; i <= v; i++)
dp[i] = -inf;
for(int i = 1; i <= cnt; i++) {
for(int j = v; j >= 0; j--) {
if(j - c[i] >= 0)
dp[j] = max(dp[j], dp[j-c[i]] + w[i]);
if(dp[v] > 0) {
ok = 1;
goto flag;
}
}
}
if(dp[v] > 0) ok = 1;
flag:printf("Collection #%d:n", ca++);
puts(ok ? "Can be divided." : "Can't be divided.");
printf("n");
}
return 0;
}

最后

以上就是甜美钢笔为你收集整理的HDOJ 1059 Dividing (多重背包例题)的全部内容，希望文章能够帮你解决HDOJ 1059 Dividing (多重背包例题)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。