本文主要是介绍小明的积木 状压dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
小明的积木
题目描述
小明酷爱搭积木，他用积木搭了 n n n 辆重量为 w i w_i wi 的小车和一艘最大载重量为 W W W 的小船，他想用这艘小船将 n n n 辆小车运输过河。每次小船运载的小车重量不能超过 W W W。另外，小船在运载小车时， 每辆小车会对小船有一个损坏值 s i s_i si，当多辆小车一起运载时，该趟运载对小船的损坏值为船上所有小车的最大损坏值。
现在小明想知道，如何用小船运载 n n n 辆小车，可以使得对小船造成的总损坏值最小。
输入描述
第一行输入两个数 W W W 和 n ( 100 ≤ W ≤ 400 ， 1 ≤ n ≤ 16 ) n (100 ≤ W ≤ 400，1 ≤ n ≤ 16) n(100≤W≤400，1≤n≤16)，分别表示小船的最大载重量和小车总数。接下来输入 n n n 行，每行输入两个整数 s i s_i si 和 w i ( 1 ≤ s i ≤ 50 ， 10 ≤ w i ≤ 100 ) w_i (1 ≤ s_i ≤ 50，10 ≤ w_i ≤100) wi(1≤si≤50，10≤wi≤100)，分别表示每辆小车对小船的损坏值和每辆小车的重量。
输出描述
输出一行，输出一个整数，表示用小船运载 n n n 辆小车，最小的总损坏值。
用例输入 1
90 4
32 50
15 20
40 50
13 40
用例输出 1
72
代码
#include <bits/stdc++.h>
using namespace std;
#define max_Heap(x) priority_queue<x, vector<x>, less<x>>
#define min_Heap(x) priority_queue<x, vector<x>, greater<x>>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
const double PI = acos(-1);int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int capacity, n;cin >> capacity >> n;int dp[(1 << n)]; // 状态压缩，dp表示所有二进制位为1的小车全部运送过去造成的最小的总损坏值memset(dp, 0x3f, sizeof(dp)); // 初始化为正无穷vector<int> s(n); // 每辆小车造成的损坏值vector<int> w(n); // 每辆小车的重量for (int i = 0; i < n; i++){cin >> s[i] >> w[i];}for (int i = 0; i < (1 << n); i++){int max_s = 0;int sum_w = 0;for (int j = 0; j < n; j++){if ((i >> j) & 1){max_s = max(max_s, s[j]); // 这些小车中可造成的最大的损坏值sum_w += w[j]; // 这些小车总重量}}if (sum_w <= capacity) // 如果当前状态的小车可一次运载完成，其造成的最小损坏值即为小车中可造成的最大的损坏值{dp[i] = max_s;}else // 不可一次运载，则需拆成两次运载，即找到该状态的所有一次划分中最小的总损坏值{for (int j = ((i - 1) & i); j > 0; j = ((j - 1) & i)) // 将车子状态i拆成子车子状态j和子车子状态j^i{dp[i] = min(dp[i], dp[j] + dp[j ^ i]);}}}cout << dp[(1 << n) - 1]; // 输出运载所有小车的最小的总损坏值return 0;
}
这篇关于小明的积木 状压dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
