首页 > 代码库 > hdu 3217 Health（状态压缩DP）

hdu 3217 Health（状态压缩DP）

2024-07-16 04:24:04   222人阅读

Health

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 527    Accepted Submission(s): 145


Problem Description
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 have side effect. 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 be healthy as quickly as possible, so the final effect of the medicines he takes should be as large as possible. Of course, YY may choose taking nothing to have a zero final effect, if he is too unlucky to achieve a positive one…
 

 

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
 
题意：刚开始题目有点看不懂，意思就是有一些药物，可能有副作用，也有积极作用。
输入时，给出一个N，表示共有几种药物，给出M表示接下来有几行描述
然后是M行，包括S， 和V， S表示集合且要把它转化为二进制看。
比如样例中表示有2种药，然后3行描述，
1 10 表示 集合1转化为2进制是01（加前导0） 表示这个集合没有第一种药物有第二种药物 且作用为10
2 -1 表示 集合2转化为2进制是10，表示这个集合有第一种药物没有第二种药物，且作用为-1
3 100就表示集合3 转化为2进制是11 表示2种药物都有，且作用为100.
要求就是选一个集合出来，这个集合和所有它的子集的作用之和最大。
 
思路：还是不太会做状态压缩DP,看了题解才知道怎么表示状态转移。
dp[i][j]， i表示规划到第几步（第几位，因为状态压缩且N最大为15）时状态为j时的最大值。
那么最开始给出的值就是dp[0][s] = v;
 
接着从第一位开始规划到第N位。
如果第i位这个药被选择了的话 dp[i][j] = dp[i-1][j] + dp[i-1][j - (1<<(i-1))] 
分为两部分，第二部分表示，如果这个药被选了那么必定要包含其他子集，所以要把这个状态中的这一位置为0
如果第i位这个药没有被选的话，dp[i][j] = dp[i-1][j].
 
举例来说 比如说
样例中dp[0][01] = 10;  dp[0][10] = -1 dp[0][11] = 100;
dp[1][01] = dp[0][01] + dp[0][00 = 10 //第一位被选了，即子集为其本身和空集。
dp[1][10] = dp[0][10] = -1 //这位没有被选的话，还是原来的结果。
dp[1][11] = dp[0][11] + dp[0][10] = 100 + (-1) = 99;
 
dp[2][01] = dp[1][01] = 10;
dp[2][10] = dp[1][10] + dp[1][00] = -1;
dp[2][11] = dp[1][11] + dp[1][01] = 99 + 10 = 109;//所以最大就是dp[2][11],即集合为2个药都选。
 
 
 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <string> 5 using namespace std; 6 #define maxn 18 7 int dp[maxn][1<<18]; 8 int N, M, s, v; 9 int main(){10     while(scanf("%d", &N) && N){11         scanf("%d", &M);12         memset(dp, 0, sizeof(dp));13         for(int i = 1; i <= M; i++){14             scanf("%d%d", &s, &v);15             dp[0][s] = v;16         }17         for(int i = 1; i <= N; i++){18             for(int sta = 0; sta < (1<<N); sta++ ){19                 if(sta & 1<<(i-1)) dp[i][sta] = dp[i-1][sta] + dp[i-1][sta-(1<<(i-1))];20                 else dp[i][sta] = dp[i-1][sta];21             }22         }23         int max = -9999;24         for(int sta = 0; sta < (1<<N); sta++){25             if(dp[N][sta] > max) max = dp[N][sta];26         }27         printf("%d\n", max);28                 29     }     30     return 0;31 }

 

 
dp[2][10] = dp[1][10] + dp[2]


联系
我们