题目大意：
给你6种石头，包括每种石头的个数，求是否可以将这些石头平分
.......................................
这题很简单的多重背包！！！
具体有多简单？
一般的多重背包用暴力肯定超时！！！
然而这道题用暴力稍微优化一点点不会超时！！！！！
然而我超时！！！
我用的多重背包超时了！！！
exm？？
暴力AC代码：
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <iostream> #include <algorithm> #include <climits> #include <queue> #define ll long long using namespace std; int dp[120005],w[10]; int main(void) { int ans,sum,cnt = 1; while(scanf("%d",&w[1]) != -1) { sum = 0; ans = 0; if(w[1] != 0) ans= 1; sum += w[1]; for(int i = 2; i <= 6; i++) { scanf("%d",&w[i]); sum += w[i]*i; if(w[i]) ans = 1; } if(!ans) break; if(sum % 2 == 1) { printf("Collection #%d:\nCan't be divided.\n\n",cnt++); } else { memset(dp,0,sizeof(dp)); for(int i = 0; i <= w[i] && i <= sum/2; i++) dp[i] = 1; for(int i = 2; i <= 6; i++) for(int j = sum/2; j >= 0; j--) { if(dp[j] == 0) continue; for(int k = 1; k <= w[i] && k *i+j <= sum/2; k++) { if(dp[k*i+j]) break; dp[k*i+j] = 1; } } if(dp[sum/2] == 1) printf("Collection #%d:\nCan be divided.\n\n",cnt++); else printf("Collection #%d:\nCan't be divided.\n\n",cnt++); } } return 0; } 找了半天才发现数组开小了！！！好吧，提示是TL我根本没往RE方面想
心态炸了！
多重背包AC代码：
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int num[8]; int dp[120005]; int step=1,k=1; int w[10000]; void divild(int i,int n) { while(n>1) { int a=(n+1)/2; int b=n/2; w[k++]=a*i; n=b; } w[k++]=i; } int main() { while(scanf("%d%d%d%d%d%d",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6])!=EOF) { if(num[1]==0&&num[2]==0&&num[3]==0&&num[4]==0&&num[5]==0&&num[6]==0) { break; } int sum=0,ans=0; k=1; for(int i=1; i<=6; i++) { sum+=num[i]; ans+=num[i]*i; if(num[i]!=0) { divild(i,num[i]); } } // for(int i=1; i<k; i++) // { // printf("%d\n",w[i]); // } int m=ans/2; if(ans%2!=0) { printf("Collection #%d:\nCan't be divided.\n\n",step++); continue; } for(int i=1; i<=m; i++) { dp[i]=-9999999; } dp[0]=0; for(int i=1; i<k; i++) { for(int j=m; j>=w[i]; j--) { dp[j]=max(dp[j],dp[j-w[i]]+1); } } if(dp[m]>0) printf("Collection #%d:\nCan be divided.\n\n",step++); else printf("Collection #%d:\nCan't be divided.\n\n",step++); } }
