思路:总共有2^10的状态,枚举每一个状态用01背包判断是否此状态可以一次运走,并记录下来,接下来又用每一个可以一趟就运走的状态看成一个01背包问题中要装的物品,求出最小的运送的次数。
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define CL(a,b) memset(a,b,sizeof(a))
#define MIN(a,b) a<b?a:b
#define MAX(a,b) a>b?a:b
using namespace std;
const int M(107);
int c1,c2,a[M],f[M],n;
int state[1200],dp[1200];
inline bool judge(int s)
{
int i,sum=0,j;
CL(f,0);
for(i=0;i<n;i++)
if(s&(1<<i))
{
sum+=a[i];
for(j=c1;j>=a[i];j--)
f[j]=MAX(f[j-a[i]]+a[i],f[j]);
}
if(sum-f[c1]<=c2)return true;
return false;
}
int main()
{
int t,i,j,k,l;
scanf("%d",&t);
for(l=1;l<=t;l++)
{
scanf("%d%d%d",&n,&c1,&c2);
if(c1<c2)swap(c1,c2);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0,k=0;i<(1<<n);i++)
{
if(judge(i))state[k++]=i;//记录两辆车一趟可以运走的状态。
dp[i]=100000000;
}
dp[0]=0;
for(i=0;i<k;i++)
for(j=(1<<n)-1;j>=0;j--)
if(!(j&state[i]))//去除重复覆盖(重复运送同一个物品)
dp[j|state[i]]=MIN(dp[j|state[i]],dp[j]+1);
printf("Scenario #%d:\n",l);
printf("%d\n",dp[(1<<n)-1]);
if(l!=t)
printf("\n");
}
}
分享到:
相关推荐
西北工业大学POJ试题C++答案代码+课程设计
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ1184-Smart typist【搜索与状态压缩】 解题报告+AC代码
背包之01背包、完全背包、多重背包详解 Dynamic+Programming 典型的动态规划,用递归下的记忆化搜索来实现 1088 POJ 动态规划加速原理之四边形不等式 基于连通性状态压缩的动态规划问题 对一些DP题目的小结 树型动态...
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
里面有非常详细的对于POJ 2411的解题报告,相信对于初学动态规划和深度优先搜索的同学来说有很好的帮助作用。
北大POJ3411-Paid Roads【class】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ初级-所有题目AC代码+解题报告
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1750462