首页 > 代码库 > 背包问题
背包问题
1.POJ 3624
最简单的0-1背包问题,这里需要反向不断更新一维数组,防止超内存
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 #define N 3500 6 #define M 13000 7 int w[N],v[N],dp[M],n,m; 8 int main() 9 {10 scanf("%d%d",&n,&m);11 memset(dp,0,sizeof(dp));12 for(int i=1;i<=n;i++){13 scanf("%d%d",&w[i],&v[i]);14 15 for(int j=m;j>=1;j--)16 if(j>=w[i]) dp[j]=max(dp[j-w[i]]+v[i],dp[j]);17 }18 printf("%d\n",dp[m]);19 return 0;20 }
2.ZOJ 1520
果然这题目还是太简单了,大牛们都不屑于做呢,开始我都没看懂题目,只是想搜一下题目看看翻译,居然没有人写这道题的博客T T
只有查到题目分类中归在了DP水题中。。。。
只能自己想,还没半小时就ac了。。。突然感觉有点小骄傲~~貌似不能太依赖题解了
这道题目把东西放入两个包裹,跟0-1背包中的一个背包有出入
但是我只要尽可能的把其中一个背包塞满的话,那么我把剩余没塞入的总和放进另一个背包就行了
这样题目意思就清楚了
只是当做第一个背包的放入量达到最大的问题,并计算所有东西的总和
如果剩余的还比另一个包裹容量大,那么就呵呵了
如果不是,我们在DP过程中利用数组回溯每次找上一个点,将所有添入点的编号输出出来,其实这个我也想的挺纠结的,代码中这部分全部注释进行了解释
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define N 1005 6 int dp[N],fa[N],cnt[N],m,l; 7 int main() 8 { 9 while(scanf("%d%d",&m,&l)&&(m!=0||l!=0)){10 int n,w,sum=0;11 scanf("%d",&n);12 memset(dp,0,sizeof(dp));13 memset(fa,0,sizeof(fa));14 for(int i=0;i<n;i++){15 scanf("%d",&w);16 sum+=w;17 for(int j=m;j>=1;j--)18 if(j>=w)19 if(dp[j-w]+w>dp[j]) cnt[j]=i,dp[j]=dp[j-w]+w,fa[j]=j-w;//fa不断记录前一个正好插入的节点的位置20 //cnt[]记录正好插入的那个节点id是什么21 }22 if(dp[m]+l<sum) printf("Impossible to distribute\n");23 else{24 int ans=dp[m];25 int k[N];26 int t=0;27 //不断递归去找正好插入节点位置时插入的点保存进k[]中,然后反向输出出来28 while(ans!=0){29 k[t++]=cnt[ans];30 ans=fa[ans];31 }32 //printf("%d\n",dp[m]);33 printf("%d ",t);34 for(int i=t-1;i>=0;i--) printf("%d ",k[i]+1);35 printf("\n");36 }37 }38 return 0;39 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。