5E07 划分大理石 0x5E「动态规划」练习
描述
有价值分别为1..6的大理石各a[1..6]块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。其中大理石的总数不超过20000。
输入格式
有多组数据！
所以可能有多行
如果有0 0 0 0 0 0表示输入文件结束
其余的行为6个整数
输出格式
有多少行可行数据就有几行输出
如果划分成功，输出Can，否则Can't
样例输入
4 7 4 5 9 1
9 8 1 7 2 4
6 6 8 5 9 2
1 6 6 1 0 7
5 9 3 8 8 4
0 0 0 0 0 0
样例输出
Can't
Can
Can't
Can't
Can
题意：
有六种石子，价值是1-6，每种石子有一个数量。现在想把他们平分为价值相等的两堆，问是否可行。
思路：
首先统计一下总的价值，如果价值是奇数，肯定是不行的。
如果价值是偶数，就是一个多重背包问题。
所以先把每种石头用二进制拆分，价值即是价值又是重量。最后看dp[mid]是否等于mid就可以了。
//#include <bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stdio.h>
#include<cstring>
#include<vector>
#include<map>
#include<set> #define inf 0x3f3f3f3f
using namespace std;
typedef long long LL; int stone[], dp[];
int num[], cnt; void split(int n, int v)
{
int x = , tmp = ;
while(tmp <= n){
num[cnt++] = x * v;
x *= ;
tmp += x;
}
x = n - tmp;
if(x){
num[cnt++] = x * v;
}
} int main(){
while(true){
int sum = ;
for(int i = ; i <= ; i++){
scanf("%d", &stone[i]);
sum += stone[i] * i;
//dp[i][0] = true;
}
if(sum == ){
break;
} if(sum % ){
printf("Can't\n");
continue;
} cnt = ;
for(int i = ; i <= ; i++){
split(stone[i], i);
}
memset(dp, , sizeof(dp));
int mid = sum / ;
for(int i = ; i < cnt; i++){
for(int j = mid; j >= num[i]; j--){
dp[j] = max(dp[j], dp[j - num[i]] + num[i]);
}
} if(dp[mid] == mid){
printf("Can\n");
}
else{
printf("Can't\n");
}
}
return ;
}