題意：有分別價值為1,2,3,4,5,6的6種物品，輸入6個數字，表示相應價值的物品的數量，問一下能不能將物品分成兩份，是兩份的總價值相等，其中一個物品不能切開，只能分給其中的某一方，當輸入六個0是（即沒有物品了），這程序結束，總物品的總個數不超過20000。
做法：
多重背包+二進制優化。
注意：
1，注意初始化dp為-1，dp[0]=0;
2，注意理清各個變量代表的含義。
[html]
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#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)<c?min(a,b):c)
#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<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
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<num)
{
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<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#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)<c?min(a,b):c)
#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<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
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<num)
{
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;
}
