本文共 1103 字,大约阅读时间需要 3 分钟。
链接:
题意:
有N件物品和两辆车,每辆车有个重量上限,现在要搬家且每次从老家到新家都是两车同时出动,问你至少需要多少次能搬完?
思路:
先看对于a1-ak的物品是否能够全部装下,先用dp的01背包看c1装下最大量后c2能否装下。
之后再利用状态压缩dp,代码中可行组合为cnt,ok[i]=j表示第i个可行的组合为j个,令dp[i][j]=y表示决策完前i个可行组合,再选择j时,最少为y次运输。
AC代码:
#include<cstdio>
#include<cstring> #include<algorithm> using namespace std; const int MAXN=1100; const int INF=1e8; int n,c1,c2,w[15]; int ok[MAXN],dp[MAXN],cnt; bool good(int st) { int f[110]; memset(f,0,sizeof(f));//f[i]=j 表示容量为i的车最多能装j重的物品 int sum=0; for(int i=0;i<n;i++)if(st&(1<<i)) { sum +=w[i]; for(int j=c1;j>=w[i];j--) { f[j] = max(f[j] , f[j-w[i]]+w[i]); } } if(sum>c1+c2) return false; for(int j=c1;j>=0;j--) if(sum-f[j]<=c2) return true; return false; } int main() { int T; scanf("%d",&T); for(int kase=1;kase<=T;kase++) { scanf("%d%d%d",&n,&c1,&c2); for(int i=0;i<n;i++) scanf("%d",&w[i]); cnt=0; for(int i=0;i<(1<<n);i++) if(good(i)) ok[cnt++]=i; for(int j=0;j<(1<<n);j++) dp[j]=INF; dp[0]=0; for(int i=0;i<cnt;i++)//松弛 { for(int j=0;j<(1<<n);j++)if( !(j&ok[i]) ) { dp[j|(ok[i])] = min(dp[j|(ok[i])] , dp[j]+1); } } printf("Scenario #%d:\n%d\n\n",kase,dp[(1<<n)-1]); } }转载地址:http://jomwi.baihongyu.com/