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
比賽的時(shí)候，看到這道題過(guò)的人很多，但是自己卻沒(méi)什么思路，非常郁悶，一看題就知道肯定是個(gè)DP,可是究竟怎么動(dòng)態(tài)規(guī)劃呢？想了半天也想不出來(lái)，一直卡在這個(gè)題上，后來(lái)有個(gè)同學(xué)提示了我方法，這才明白過(guò)來(lái)，原來(lái)這里面還有位運(yùn)算，看來(lái)我平時(shí)缺少位運(yùn)算方面的訓(xùn)練了。。。哎 我還是太水。。。
分析：這個(gè)題的DP思想是把所有1 to 2^n-1的狀態(tài)所對(duì)應(yīng)的健康值都算出來(lái)，然后再其中取一個(gè)最大值。我們看看他是如何狀態(tài)轉(zhuǎn)移的：
假設(shè) n=3 現(xiàn)在考慮 1 1 1(7，從左到右分別是第3，2，1種藥品) 這種狀態(tài)，如果第三種藥品不使用，那么相當(dāng)于0 1 1 產(chǎn)生的 總健康值；
這個(gè)健康值已經(jīng)由它的子結(jié)構(gòu)得到。
如果使用第三種藥品，那么我們進(jìn)行一次DFS，將他對(duì)應(yīng)的所有的有效狀態(tài)（無(wú)效狀態(tài)對(duì)應(yīng)為0即可）對(duì)應(yīng)的健康值加起來(lái)，這樣就得到了
使用第三種藥物的總健康值。
我們將上述子結(jié)構(gòu)和DFS得到的結(jié)果相加，便得到了當(dāng)前狀態(tài)下的總健康值。
我們做一個(gè)循環(huán)，i from 1to 2^n-1 ,把所有情況對(duì)應(yīng)的健康值算出來(lái)，然后再其中取一個(gè)最大值即可。（位運(yùn)算很重要！）
#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;
}
做了這個(gè)題，突然想起了將10進(jìn)制轉(zhuǎn)化成2進(jìn)制的方法，不斷模除2，取余數(shù)，但是一直沒(méi)有深究，今天終于明白了，原來(lái)如果把這個(gè)十進(jìn)制數(shù)考慮成2進(jìn)制，右移一位相當(dāng)于除以2，模除2就是把最后那一位給取出來(lái)了，不斷的模除2，就把這個(gè)2進(jìn)制數(shù)一位一位的取出。
PS :感謝那位提示我思路的同學(xué)