首页 > 代码库 > 背包问题

背包问题

2024-07-16 19:09:22   223人阅读

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 }

 


联系
我们