题目类型 DP
题目意思
给出最多10件物品 (重量在1-100之间) 有两辆载重分别是C1和C2的车 (1 <= C1, C2 <= 100)
问这两辆车要拉多少次才能把所有物品拉走(一次就是把尽量多的物品分别放在两辆车上开走, 物品不能分割)
解题方法
只有10个物品那么少 果断偏暴力解决
首先用状态压缩把 某几个物品的集合压缩成一个数字 (例如物品 1 对应 1, 物品 2 对应 2, 物品 3, 对应 4 那么物品1和3组成的物品集合对应的数字就是5
如果 ( 5 & (1<<(x-1)) ) 为非0的话说明 5 表示的集合中包含第 x 个物品
然后用一个数组 dp[i] 表示把 i 这个集合的物品运走所需的最少次数
那么对于某一次拉走的物品集合 j 就有转移式 dp[ i | j ] = min(dp[ i | j ], dp[i] + 1); (其中集合 i 和 j 没有相同的物品) (和代码的转移式其实是等价的)
判断某个集合 j 能否一次被拉走 直接枚举这个集合的子集, 即这个子集给C1拉走, j剩下的集合元素则被C2拉走 如果重量符合即合法 详细见代码
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 1<<30;
int n, c1, c2;
int A[20];
int dp[1100];
bool Judge(int x) { // 判断 x 这个集合的物品能否一次被两辆车拉走
int B[20], nb = 0, S = 0;
for( int i=0; i<n; i++ ) if(x & (1<<i)) S += A[i], B[nb++] = i; // 处理出 x 包含的物品
for( int i=0; i<(1<<nb); i++ ) { // 枚举 x 这个集合的子集
int sum = 0;
for( int j=0; j<nb; j++ ) {
if(i & (1<<j)) sum += A[B[j]]; // sum 表示被 C1 拉走的物品的重量和
}
if(sum <= c1 && S - sum <= c2) return true; // S - sum 则表示被C2拉走的物品的重量和
if(sum <= c2 && S - sum <= c1) return true;
}
return false;
}
int main() {
//freopen("in", "r", stdin);
int t, cnt = 1;
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n, &c1, &c2);
for( int i=0; i<n; i++ ) scanf("%d", &A[i]);
for( int i=0; i<(1<<n); i++ ) dp[i] = INF;
dp[0] = 0;
for( int i=0; i<(1<<n); i++ ) { // 枚举要一次拉走的物品集合 i
if(Judge(i)) { // 如果 集合 i 合法
for( int j=0; j<(1<<n); j++ ) { // 枚举可被 i 更新的集合 j
if((j & i) == i) { // 如果 j 包含 i 说明 j 合法
if(dp[j] > dp[j^i] + 1) {
dp[j] = dp[j^i] + 1;
}
}
}
}
}
printf("Scenario #%d:\n", cnt++);
printf("%d\n\n", dp[(1<<n)-1]);
}
return 0;
}