Consumer -- 依赖背包

http://acm.hdu.edu.cn/showproblem.php?pid=3449 Consumer
#include <cmath>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define CLR(c,v) (memset(c,v,sizeof(c)))

template <typename _T>
_T Max(_T a,_T b){
	return a<b?b:a;
}
template <typename _T>
_T Max(_T a,_T b,_T c){
	return a<Max(b,c)?Max(b,c):a;
}

const int inf = -(1<<30);
const int INF =  (1<<30);
const int M   =  1e6 + 10;

int n_set,max_cost;
int c[M];
int v[M];
int dp[M]; 
int res[M];

void ZeroOnePack(int cost,int value,int max_cost,int set,int box_cost){
	int bound = cost + box_cost;
	for(int i = max_cost ; i >= bound ; i--)
		dp[i] = Max(dp[i],dp[i-cost]+value);
}


int main()
{
	//freopen("in.txt","r",stdin);
	while(cin >> n_set >> max_cost){
		CLR(dp,0);CLR(res,0);
		for(int i = 1 ; i <= n_set ; i++){
			int box_cost,n,cost,value;
			cin >> box_cost >> n;
			for (int j = 0 ; j <= max_cost-box_cost ; j++) // 先放盒子
				dp[j+box_cost] = res[j];

			for (int j = 1 ; j <= n ; j++){
				cin >> cost >> value;
				ZeroOnePack(cost,value,max_cost,i,box_cost);
			}
			for(int j = 1 ; j <= max_cost ; j++) // 状态转移
				res[j] = Max(dp[j],res[j]);
		}
		cout << res[max_cost] << endl;
	}
	return 0;
}

（编辑：商洛站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!