poj-1014-多重背包+二进制优化 - c++编程基础

题意：有分别价值为1,2,3,4,5,6的6种物品，输入6个数字，表示相应价值的物品的数量，问一下能不能将物品分成两份，是两份的总价值相等，其中一个物品不能切开，只能分给其中的某一方，当输入六个0是（即没有物品了），这程序结束，总物品的总个数不超过20000。

做法：

多重背包+二进制优化。

注意：

1，注意初始化dp为-1，dp[0]=0;

2，注意理清各个变量代表的含义。

[html]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INT_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c max(a,b):c)
#define min3(a,b,c) (min(a,b) #define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{
int u;
int v;
int w;
bool friend operator < (node a, node b){
return a.w < b.w;
}
}edge[1001];
int gcd(int n,int m){if(n int lcm(int n,int m){if(n int n[7];
int w[7];
int c[7];
int dp[1000001];
int leap=0;
int s;
void pack01(int cost ,int weight)
{
int v;
for(v=s/2;v>=weight;v--)
{
dp[v]=max(dp[v],dp[v-weight]+cost);
if(dp[v]==s/2)
{
leap=1;
return ;
}
}
}
void mul(int cost,int num)
{
if(cost*num>s/2)
{
num=(s/2)/cost;
}
int k=1;
while(k {
pack01(cost*k,cost*k);
if(leap)return ;
num=num-k;
k=k*2;
}
pack01(cost*num,cost*num);
}
int main()
{
int i;
for(i=1;i<=6;i++)
w[i]=i,c[i]=1;
int t;
t=0;
while(1)
{
s=0;
for(i=1;i<=6;i++)
{
scanf("%d",&n[i]);
s+=n[i]*w[i];
}
if(s==0)break;
t++;
leap=0;
printf("Collection #%d:\n",t);
if(s%2==0)
{
memset(dp,-1,sizeof(dp));
dp[0]=0;
for(i=1;i<=6;i++)
{
mul(w[i],n[i]);
if(leap)break;
}
}
if(leap)
printf("Can be divided.\n\n");
else
printf("Can't be divided.\n\n");
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INT_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c max(a,b):c)
#define min3(a,b,c) (min(a,b) #define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{
int u;
int v;
int w;
bool friend operator < (node a, node b){
return a.w < b.w;
}
}edge[1001];
int gcd(int n,int m){if(n int lcm(int n,int m){if(n int n[7];
int w[7];
int c[7];
int dp[1000001];
int leap=0;
int s;
void pack01(int cost ,int weight)
{
int v;
for(v=s/2;v>=weight;v--)
{
dp[v]=max(dp[v],dp[v-weight]+cost);
if(dp[v]==s/2)
{
leap=1;
return ;
}
}
}
void mul(int cost,int num)
{
if(cost*num>s/2)
{
num=(s/2)/cost;
}
int k=1;
while(k {
pack01(cost*k,cost*k);
if(leap)return ;
num=num-k;
k=k*2;
}
pack01(cost*num,cost*num);
}
int main()
{
int i;
for(i=1;i<=6;i++)
w[i]=i,c[i]=1;
int t;
t=0;
while(1)
{
s=0;
for(i=1;i<=6;i++)
{
scanf("%d",&n[i]);
s+=n[i]*w[i];
}
if(s==0)break;
t++;
leap=0;
printf("Collection #%d:\n",t);
if(s%2==0)
{
memset(dp,-1,sizeof(dp));
dp[0]=0;
for(i=1;i<=6;i++)
{
mul(w[i],n[i]);
if(leap)break;
}
}
if(leap)
printf("Can be divided.\n\n");
else

poj-1014-多重背包+二进制优化 (一)