这题的题意是 在双脚天平上有N块东西，依次从上面取走一些，最后使得这个天平保持平衡！
解题：
逆着来依次放入，如果可行那就可以，记得得有木板自身的重量。
/*************************************************************************
> File Name: 10123.cpp
> Author: opas
> Mail: [email protected]
> Created Time: 2016年10月22日 星期六 22时58分53秒
************************************************************************/
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxm = ;
const int maxn = <<maxm;
struct Node {
int id,weight,dist;
Node (int l_id = , int l_weight = , int l_dist = ) {
id = l_id;
weight = l_weight;
dist = l_dist;
}
bool operator < (const Node A)const {
if (weight != A.weight ) return weight < A.weight;
return id < A.id;
}
}package[maxm];
int dp[maxn];
int weight_val[maxn][];
int ans[maxm];
void InitVal(int n) {
int max_val = <<n;
for(int i = ; i < max_val; ++ i) {
dp[i] = ;
}
}
int length ,weight, num_package;
void AddPackage(int per_status ,int now_status, int id) {
for ( int i = ; i < ; ++ i)
weight_val[now_status][i] = weight_val[per_status][i];
if(package[id].dist <= -) {
weight_val[now_status][] = weight_val[per_status][] + - ( package[id].dist + ) * package[id].weight;
weight_val[now_status][] = weight_val[per_status][] + - ( package[id].dist - ) * package[id].weight;
}else if(package[id].dist < ){
weight_val[now_status][] = weight_val[per_status][] + (package[id].dist + ) * package[id].weight;
weight_val[now_status][] = weight_val[per_status][] + - (package[id].dist - ) * package[id].weight;
}else{
weight_val[now_status][] = weight_val[per_status][] + (package[id].dist + )*package[id].weight;
weight_val[now_status][] = weight_val[per_status][] + (package[id].dist - )*package[id].weight;
}
}
int CheckPackage(int now_status) {
int l_val1 = weight_val[now_status][];
int l_val2 = weight_val[now_status][] + * weight;
if(l_val1 > l_val2){
return dp[now_status] = ;
}
l_val1 = weight_val[now_status][];
l_val2 = weight_val[now_status][] + * weight;
if(l_val1 > l_val2) {
return dp[now_status] = ;
}
return dp[now_status] = ;
}
int dfs(int now_loc, int now_status) {
if(now_loc == num_package) {
return ;
}
dp[now_status] = ;
for(int i = ; i< num_package ; ++ i) {
if(now_status & (<<i))
continue;
int next_status = now_status | (<<i);
if(dp[next_status] == ) return dp[next_status];
AddPackage(now_status, next_status, i);
if(CheckPackage(next_status) == )
continue;
ans[now_loc] = i;
if (dfs(now_loc+, next_status) == ) {
return dp[now_status]=;
}
}
return ;
}
int main(){
for(int cc = ; ; ++ cc) {
cin>>length>>weight>>num_package;
if(length + weight + num_package == )
break;
InitVal(num_package);
for(int i = ; i < num_package; ++ i) {
int l_weight , l_dist;
scanf("%d%d",&l_dist, &l_weight);
l_dist = l_dist * ;
package[i] = Node(i, l_weight, l_dist);
}
printf("Case %d:\n",cc);
if( dfs( , ) == ) {
for(int i = num_package - ; i >= ; -- i) {
printf("%d %d\n", package[ans[i]].dist/, package[ans[i]].weight);
}
}else{
printf("Impossible\n");
}
}
return ;
}