首页 > 代码库 > 背包/母函数？/二分思想？

背包/母函数？/二分思想？

2024-09-11 00:04:20   217人阅读

1033: 空运物资

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 4
[提交][状态][讨论版][Edit] [TestData]

题目描述

在灾区，多数人已经受伤，缺水，少食物，精神处在崩溃的边缘。很多人的生存条件仅能维持几天。灾民需要帐篷、衣物、食品和医疗器材、药品等物资。14日上午，中央军委委员、空军司令员许其亮组织召开空军首长办公会，将空军下一步救灾重点确定为抢救伤员、空投、空运。空军各部队都派出多架运输机，准备向灾区空运急需物品。
现在已知四种打包过的急需物品重量分别为C1, C2, C3,C4 ，数量分别为M1，M2，M3，M4包。一架运输机的载重量为W, 现在各部队关心将一架运输机装满共有多少种运载方案，以便调度进行空运。
比如C={ 100, 200, 500, 1000}, M={ 3, 2, 3, 1 }, W=1000, 一共有4种运载方案:
1000=100+100+100+200+500
1000=100+200+200+500
1000=500+500
1000=1000

输入

第一行： C1 C2 C3 C4 N    其中N为空运的部队数
接下来n行： Mi1 Mi2 Mi3 Mi4 Wi    表示各运载部队需空运的4种物品数量Mi和各自运输机的载重量Wi i=1,2,….. , N

输出

输出有N行，表示各部队运载物品的方案总数，保证答案在10000范围内

【约束条件】
（1）0< Cj <= 1000 0 <= Mij <= 500 i =1,2,….. , N j =1,2,3,4
（2）N<=1000 0 < Wi <= 100000 i =1,2,….. , N
（3）时间限制： 1000MS

 

样例输入

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

样例输出

4
27

背包写的代码感觉数据强点肯定WA竟然过了，后来hxw说可以换种思想，不比拘泥于一种形式。
这道题不同以往的背包问题，他告诉我们固定的四件物品，而不是n件，所以我们可以两件两件的考虑最后计算总值；
由于物品数量最大500，所以这样做的话大大节约了复杂度。

#include<bits/stdc++.h>
using namespace std;
#define ql(a) memset(a,0,sizeof(a))
int a1[100005],a2[100005];
int main()
{
int C[5],N,i,j,k;
int M[5],W;
while(cin>>C[1]>>C[2]>>C[3]>>C[4]>>N){
while(N--){int s=0;
memset(a1,0,sizeof(a1));
memset(a2,0,sizeof(a2));
cin>>M[1]>>M[2]>>M[3]>>M[4]>>W;
for(i=0;i<=M[1];++i)
for(j=0;j<=M[2];++j)
if(C[1]*i+C[2]*j<=W) a1[C[1]*i+C[2]*j]++;          //前两件物品的方案
for(i=0;i<=M[3];++i)
for(j=0;j<=M[4];++j)
if(C[3]*i+C[4]*j<=W) a2[C[3]*i+C[4]*j]++;          //后两件的方案
for(i=0;i<=W;++i)
s+=a1[i]*a2[W-i];                                                   //组合问题
cout<<s<<endl;
}
}
return 0;
}

 

 

 

背包代码：

#include<bits/stdc++.h>
using namespace std;
int dp[100005];
int main()
{
    int n,i,j,k,w,q;
    int c[6],m[6];
    while(cin>>c[1]>>c[2]>>c[3]>>c[4]>>n){
        while(n--){
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        cin>>m[1]>>m[2]>>m[3]>>m[4]>>w;
 
        for(i=1;i<=4;++i){
            for(j=w;j>=c[i];--j)                     //w最大10w，这样的话有可能TLE。。。10w*500.。。
              for(k=1;k<=m[i];++k)
            if(j>=k*c[i]) dp[j]+=dp[j-k*c[i]];
        }
        cout<<dp[w]<<endl;
        }
    }
    return 0;
}
 
顺手母函数：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 100010
int c1[N+10],c2[N+10],c[4],m[4];
int main()
{
    int i,n,j,k,w;
    while(scanf("%d %d %d %d %d",&c[0],&c[1],&c[2],&c[3],&n)!=EOF)
        {
        while(n--)
            {
            for(i=0;i<4;i++)
            {
                scanf("%d",&m[i]);
            }
            scanf("%d",&w);
            memset(c1,0,sizeof(int)*(w+10));
            memset(c2,0,sizeof(int)*(w+10));
            for(i=0,j=0;i<=m[0];i++,j+=c[0])
                c1[j]=1;
            for(i=1;i<4;i++){
                for(j=0;j<=w;j++) {
                   if(c1[j]==0) continue;
                   for(k=0;k+j<=w&&k<=m[i];k++) {
                        c2[k*c[i]+j]+=c1[j];
                   }
                }
                for(j=0;j<=w;j++) {
                    c1[j]=c2[j];
                    c2[j]=0;
                }
            }
            printf("%d\n",c1[w]);
        }
    }
    return 0;
}
 

背包/母函数？/二分思想？


联系
我们