I - Relocation
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit StatusDescription
Emma and Eric are moving to their new house they bought after returning from their honeymoon. Fortunately, they have a few friends helping them relocate. To move the furniture, they only have two compact cars, which complicates everything a bit. Since the furniture does not fit into the cars, Eric wants to put them on top of the cars. However, both cars only support a certain weight on their roof, so they will have to do several trips to transport everything. The schedule for the move is planed like this:
At their old place, they will put furniture on both cars.
Then, they will drive to their new place with the two cars and carry the furniture upstairs.
Finally, everybody will return to their old place and the process continues until everything is moved to the new place.
Note, that the group is always staying together so that they can have more fun and nobody feels lonely. Since the distance between the houses is quite large, Eric wants to make as few trips as possible.
Given the weights wi of each individual piece of furniture and the capacities C1 and C2 of the two cars, how many trips to the new house does the party have to make to move all the furniture? If a car has capacity C, the sum of the weights of all the furniture it loads for one trip can be at most C.
Input
The first line contains the number of scenarios. Each scenario consists of one line containing three numbers n, C1 and C2. C1 and C2 are the capacities of the cars (1 ≤ Ci ≤ 100) and n is the number of pieces of furniture (1 ≤ n ≤ 10). The following line will contain n integers w1, …, wn, the weights of the furniture (1 ≤ wi ≤ 100). It is guaranteed that each piece of furniture can be loaded by at least one of the two cars.
Output
The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line with the number of trips to the new house they have to make to move all the furniture. Terminate each scenario with a blank line.
Sample Input
2
6 12 13
3 9 13 3 10 11
7 1 100
1 2 33 50 50 67 98Sample Output
Scenario #1:
2
Scenario #2:
/*狀態壓縮加ＤＰ就是把一次能運走的，當成一個物品<PRE><SPAN style="COLOR: rgb(0,128,0)">總狀態量為1<<n，判斷這些狀態集合裡的那些物品能否一次就 運走，如果能運走，那就把這個狀態看成一個物品。預處理完能 從枚舉中找到tot個物品，再用這tol個物品中沒有交集 （也就是兩個狀態不能同時含有一個物品）的物品進 行01背包，每個物品的體積是state[i]，can函數，就是判斷能否一次把給定的物品運走！注意位運算的順序！</SPAN></PRE><PRE><SPAN style="COLOR: rgb(0,128,0)">2、“按位或”運算符（|） 兩個相應的二進制位中只要有一個為1，該位的結果值為1。借用邏輯學中或運算的話來說就是，一真為真</SPAN></PRE><PRE><SPAN style="COLOR: rgb(0,128,0)">左移運算符（<<） 左移運算符是用來將一個數的各二進制位左移若干位，移動的位數由右操作數指定（右操作數必須是非負</SPAN></PRE><PRE><SPAN style="COLOR: rgb(0,128,0)">右移運算符（>>） 右移運算符是用來將一個數的各二進制位右移若干位，移動的位數由右操作數指定（右操作數必須是非負 值），移到右端的低位被捨棄，對於無符號數，高位補0。對於有符號數，某些機器將對左邊空出的部分 用符號位填補（即“算術移位”）*/</SPAN></PRE> /*狀態壓縮加ＤＰ就是把一次能運走的，當成一個物品總狀態量為1<<n，判斷這些狀態集合裡的那些物品能否一次就 運走，如果能運走，那就把這個狀態看成一個物品。預處理完能 從枚舉中找到tot個物品，再用這tol個物品中沒有交集 （也就是兩個狀態不能同時含有一個物品）的物品進 行01背包，每個物品的體積是state[i]，can函數，就是判斷能否一次把給定的物品運走！注意位運算的順序！2、“按位或”運算符（|） 兩個相應的二進制位中只要有一個為1，該位的結果值為1。借用邏輯學中或運算的話來說就是，一真為真左移運算符（<<） 左移運算符是用來將一個數的各二進制位左移若干位，移動的位數由右操作數指定（右操作數必須是非負右移運算符（>>） 右移運算符是用來將一個數的各二進制位右移若干位，移動的位數由右操作數指定（右操作數必須是非負 值），移到右端的低位被捨棄，對於無符號數，高位補0。對於有符號數，某些機器將對左邊空出的部分 用符號位填補（即“算術移位”）*/
PRE class=html name="code">//狀態壓縮加ＤＰ
#include <iostream>
#include<stdio.h> #include<cstring>
#define inf 0x4f4f4f4f
using namespace std;
int n,v1,v2;
int state[1<<11];
bool visit[200];
int cost[1<<11],dp[1<<11];
int minx(int a,int b)//返回最小值
{ if(a<b) return a;
else return b; } bool can(int x) { int i,j,sum;
memset(visit,false,sizeof(visit));
sum=0;
visit[0]=true;//一定要把０初始化為真
for(i=0;i<n;i++) {
if((1<<i)&x)//取Ｘ的第Ｉ位，判斷是否運走
{ sum+=cost[i];//要運走的總值加起來
if(sum>v1+v2)//如果一次要運的總值，比兩輛車的總容量還大，當然要去掉
{ return false; }
for(j=v1;j>=cost[i];j--)
{
if(visit[j-cost[i]])//visit[v1-cost[i]]為真說明，在前面的值會取到，這時再加一個cost [j],那麼visit[j]也能取到，所以就是為真
{
visit[j]=true;
} } } } for(i=0;i<=v1;i++)
{ if(visit[i]&&sum-i<=v2)//如果第一輛車裝了Ｉ的容量，剩下的sum-i比第二輛小，當然，可以動輸返連回真！
return true;
} return false;
} int main() { int t,total,tcase,i,v;
scanf("%d",&t);
for(tcase=1;tcase<=t;tcase++)
{ printf("Scenario #%d:\n",tcase);
scanf("%d%d%d",&n,&v1,&v2);
for(i=0;i<n;i++) { scanf("%d",&cost[i]);
} for(i=0,total=0;i<(1<<n);i++)
{ if(can(i))//判斷一次能不能把這幾個物品運走，能運走返回ＴＲＵＥ {
state[total]=i;
//總的狀態數，一個狀態，相當於一個物品，也就轉化成了背包問題 total++; } }
for(i=0;i<(1<<n);i++)
{ dp[i]=inf;//保證所有的物品都要取到
} dp[0]=0;//到此，已經成了ＤＰ問題，就是一個０１背包問題了！ for(i=0;i<total;i++)
for(v=(1<<n)-1;v>=0;v--)
{
if((state[i]&v)==0)//新加入的物品，沒有被以前的已經運走！ { if(dp[v]==inf)
continue;
dp[v|state[i]]=minx(dp[v]+1,dp[v|state[i]]);//合在一起的狀態 } }
printf("%d\n\n",dp[(1<<n)-1]);
} return 0; } </PRE><BR><BR>
