poj1014 hdu1059 Dividing 多重背包

本文主要是介绍poj1014 hdu1059 Dividing 多重背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有价值为1~6的宝物各num[i]个，求是否能分成价值相等的两部分。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll long long
#define mod 1000000007
using namespace std;int dp[120010],num[10],v;void pack01(int c,int w)
{for(int i=v;i>=c;i--)dp[i]=max(dp[i],dp[i-c]+w);
}void packall(int c,int w)
{for(int i=c;i<=v;i++)dp[i]=max(dp[i],dp[i-c]+w);
}void mulpack(int c,int w,int n)
{if(c*n>=v)packall(c,w);else{int i=1;while(i<n){pack01(c*i,w*i);n-=i;i+=i;}pack01(c*n,w*n);}
}int main()
{int cas=1,i,j,sum;//在这里多定义了一个v 导致一直出不来样例while(1){sum=0;for(i=1;i<=6;i++){scanf("%d",&num[i]);sum+=(num[i]*i);//WA}if(sum==0) break;printf("Collection #%d:\n",cas++);if(sum&1){printf("Can't be divided.\n\n");continue;}memset(dp,0,sizeof dp);v=sum/2;for(i=1;i<=6;i++)if(num[i]) mulpack(i,i,num[i]);if(dp[v]==v) printf("Can be divided.\n\n");else printf("Can't be divided.\n\n");}return 0;
}

这篇关于poj1014 hdu1059 Dividing 多重背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---