Health
Unfortunately YY gets ill, but he does not want to go to hospital. His girlfriend LMY gives him N kinds of medicine, which may be helpful. It is not a good idea to take all of them, since taking several different kinds of medicine may cause undesirable side effects. Formally speaking, for each subset S of the N kinds of medicine (excluding the empty set), it has a health value v(S). If YY chooses to take a combination T of the medicines, the final effect to his illness is the sum of health values of all non-empty subsets of T.
YY wants to get healthy as quickly as possible, so the final effect of the medicines he takes should be as great as possible. Of course, YY may choose to take nothing, thus having a zero final effect, if he is too unlucky that all other alternatives he can get are negative…
Input
Input contains multiple test cases.
For each test case, the first line contains a positive integer N (N≤16), the number of different kinds of medicine YY received from LMY.
The second line contains a single integer M (0≤M≤2N).
M lines follow, representing a list of health values.
Each of the M lines contains 2 integers, s (1≤s<2N) and v (-10000≤v≤10000), indicating a subset of the N kinds of medicine and its health value. Write s in binary representation and add leading zeros if needed to make it exactly N binary digits. If the ith binary digit of s is 1, then the subset it represents includes the ith kind of medicine; otherwise it does not.
It is guaranteed that no two lines of the list describe the same subset. All non-empty subsets that do not appear in the list have health value 0.
Input ends with N=0.
Output
For each test case, output one line with only one integer, the maximum final effect that can be achieved.
Sample Input
2
3
1 10
2 -1
3 100
0
Sample Output
109
比賽的時候，看到這道題過的人很多，但是自己卻沒什么思路，非常郁悶，一看題就知道肯定是個DP,可是究竟怎么動態(tài)規(guī)劃呢？想了半天也想不出來，一直卡在這個題上，后來有個同學提示了我方法，這才明白過來，原來這里面還有位運算，看來我平時缺少位運算方面的訓練了。。。哎 我還是太水。。。
分析：這個題的DP思想是把所有1 to 2^n-1的狀態(tài)所對應的健康值都算出來，然后再其中取一個最大值。我們看看他是如何狀態(tài)轉移的：
假設 n=3 現在考慮 1 1 1(7，從左到右分別是第3，2，1種藥品) 這種狀態(tài)，如果第三種藥品不使用，那么相當于0 1 1 產生的 總健康值；
這個健康值已經由它的子結構得到。
如果使用第三種藥品，那么我們進行一次DFS，將他對應的所有的有效狀態(tài)（無效狀態(tài)對應為0即可）對應的健康值加起來，這樣就得到了
使用第三種藥物的總健康值。
我們將上述子結構和DFS得到的結果相加，便得到了當前狀態(tài)下的總健康值。
我們做一個循環(huán)，i from 1to 2^n-1 ,把所有情況對應的健康值算出來，然后再其中取一個最大值即可。（位運算很重要！）
#include<iostream>
using namespace std;
#define MAX (1<<17)
int value[MAX];
int dp[MAX];
int bin[20];
int n,m;
int sum;
int ans;
void dfs(int i,int p)
{
if(i<0)
{
sum+=value[p];
return ;
}
else if(bin[i]==1)
dfs(i-1,p+(1<<i));
dfs(i-1,p);
}
void solve(int n)
{
int now=( (1<<n)-1 );
int i;
int j=1;
int k=-1;
for(i=1;i<=now;i++)
{
sum=0;
memset(bin,0,sizeof(bin));
j=1;
k=-1;
while(j*2<=i)
{
if(j&&i)
{
k++;
bin[k]=1;
}
else
{
k++;
bin[k]=0;
}
j*=2;
}
dfs(k,j);
dp[i]=dp[i-j]+sum;
if(dp[i]>ans)
ans=dp[i];
}
}
int main()
{
int i;
while(scanf("%d",&n))
{
ans=0;
memset(value,0,sizeof(value));
if(n==0)
break;
scanf("%d",&m);
for(i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
value[a]=b;
}
solve(n);
printf("%d\n",ans);
}
return 0;
}
做了這個題，突然想起了將10進制轉化成2進制的方法，不斷模除2，取余數，但是一直沒有深究，今天終于明白了，原來如果把這個十進制數考慮成2進制，右移一位相當于除以2，模除2就是把最后那一位給取出來了，不斷的模除2，就把這個2進制數一位一位的取出。
PS :感謝那位提示我思路的同學