状压DP拿下01背包（

userId_undefined

‮队团加不）ด้้童帅_者仇复

尊贵铂金

2024-11-10 12:19:46

发布于：广东

15阅读
0回复
0点赞

dp0,i,dp1,idp_{0,i},dp_{1,i} 分别表示第 ii 种状态的重量、最大价值

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[30], b[30];
int dp[2][33554432];
signed main(){
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
	}
	for(int i = 0; i < (1 << n); i++){
		for(int j = 0; j < n; j++){
			if((i & (1 << j)) && dp[0][i ^ (1 << j)] + a[j] <= m && dp[1][i ^ (1 << j)] + b[j] > dp[1][i]){
				dp[0][i] = dp[0][i ^ (1 << j)] + a[j];
				dp[1][i] = dp[1][i ^ (1 << j)] + b[j];
			}
		}
	}
	int mx = 0, idx = 0;
	for(int i = 0; i < (1 << n); i++){
        mx = max(mx, dp[1][i]);
	}
	cout << mx;

	return 0;
}

什么？你问这个方法有什么优点？
好吧确实没有 时间复杂度 O(2n×n)O(2^n\times n)，空间复杂度 O(2n)O(2^n) 都不如深搜（

userId_undefined
去预览
0/2000

全部评论 2

热门讨论