做题感悟:知道用背包来做但是想不出怎样用,开始就察觉 n <=10 有猫腻,百度一下果然不出所料,状态压缩+01背包。
解题思路:因为最多只有 10 件物品 so ~ > 只需要枚举出两个车可以装的所有情况,每种情况看成一个物品,价值为 1 ,怎样枚举呢? 当然要用状态压缩了,状态从 1 ~ (1<<n) -1(这样就包含了所有状态,例如:n = 3 ,状态从001 ~ 111 ,101 代表选择第一件和第三件物品的结果 ), 看每种状态是否满足两辆车装,如果满足就看成一种物品。处理好各种状态后,用 01 背包装各个物品只要没有交集(想与等于0,如果 100 就可以与 011 进行合并合并后为
111 ,代表取所有物品)就进行 DP。
状态方程: dp[ i ] = min ( dp [ i ] , dp[ i | v ] + 1 ) ; dp[ i ] 代表选择了 i 这种状态后运送的最小次数, v 代表选的状态。
代码:
#include<stdio.h> #include<iostream> #include<map> #include<stack> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; #define lld __int64 const double PI = 3.1415926 ; const double esp = 1e-7 ; const int INF = 999999999 ; const int MX = 1<<10 ; int n,m1,m2 ; bool vis[MX] ; int dp[MX],v[MX],g[15] ; bool judge(int x) // 判断是否存在这样的物品 { memset(vis,false,sizeof(vis)) ; vis[0]=true ; int sum=0 ; for(int i=0 ;i<n ;i++) if(x&(1<<i)) { sum+=g[i] ; for(int j=m1 ;j>=g[i] ;j--) if(vis[j-g[i]]) vis[j]=true ; } for(int i=0 ;i<=m1 ;i++) if(vis[i]&&sum-i<=m2) return true ; return false ; } int main() { int Tx,Case=0 ; scanf("%d",&Tx) ; while(Tx--) { scanf("%d%d%d",&n,&m1,&m2) ; for(int i=0 ;i<n ;i++) scanf("%d",&g[i]) ; int num=0 ; for(int i=1 ;i<=(1<<n)-1 ;i++) // 枚举物品 { if(judge(i)) v[num++]=i ; dp[i]=INF ; } dp[0]=0 ; for(int i=0 ;i<num ;i++) for(int j=(1<<n)-1-v[i] ;j>=0 ;j--) if((j&v[i])==0) dp[j|v[i]]=min(dp[j|v[i]],dp[j]+1) ; printf("Scenario #%d:\n",++Case) ; printf("%d\n\n",dp[(1<<n)-1]) ; } return 0 ; }