首页 > ACM题库 > HDU-杭电 > HDU 3217-Health-动态规划-[解题报告]HOJ
2014
03-07

HDU 3217-Health-动态规划-[解题报告]HOJ

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 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 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.

输出:

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.

样例输入:

2
3
1 10
2 -1
3 100
0

样例输出:

109

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3217

本题是一道状态压缩DP,题目意思很简单,就是说有n种药,为了治病可以搭配着吃,每种告诉你各种搭配及每种搭配能起到了治疗功效,当选择某种搭配的时候他的所有子搭配(即搭配的子集)的功效和就是最终效果,求给处的所有搭配的最大最终效果。

代码如下:

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn=1<<17;

int dp[17][maxn];

int max(int a,int b){
	return a>b?a:b;
}

int main(){
	int n,m,i,j;
	while(scanf("%d",&n)&&n){
		scanf("%d",&m);
		memset(dp,0,sizeof(dp));
		int s,e;
		for(int i=0;i<m;i++){
            scanf("%d%d",&s,&e);
            dp[0][s]=e;
        }
        for(i=1;i<=n;i++){
            for(j=0;j<maxn;j++){
                if(j&(1<<(i-1))){
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-(1<<(i-1))];
                }else {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
		int ans=-1<<30;
        for(i=0; i<(1<<n);i++) {
            ans = max(ans, dp[n][i]);
        }
		printf("%d\n",ans);
	}
	return 0;
}

参考:http://blog.csdn.net/iaccepted/article/details/6740917