poj1837【背包】

时间：2024-01-07 18:44:56

题意：

有一根杆子，给出一些杆子上的位置，位置上能放重物，再给出一些重物的重量。

重物都需要被使用，但是位置不一定都要用到。

问你能有多少种方法让这个杆子平衡。

思路：

在位置上是0/1背包思想，取或不取。

dp[]直接代表在该重量下有多少方案数。

最大的重量是20*25*15=7500;

因为还有负数，我们就直接2*7500;

然后看一下dp[7500]就好了。

0/1背包思想，转化为对于前i个物品在j重量有多少方案，

对于钩子，直接for一遍放一遍，更新。

ps:如果dp数组要在一维上操作，那么每次更新都要使j变大或者变小，

那么我们枚举的时候就可以不会触碰到这次更新的结果。。然而太弱，搞不出一维的。

//#include<bits/stdc++.h>

#include<cstdio>

#include<math.h>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

const double eps=1e-5;

const double pi=acos(-1.0);

const int mod=998244353;

const LL INF=0x3f3f3f3f;

const int N=25;

int dp[N][15007];

int a[N];

int b[N];

int main()

{

    int t,i,k,j;

    int c,g;

    scanf("%d%d",&c,&g);

    for(i=1;i<=c;i++)

        scanf("%d",&a[i]);

    for(i=1;i<=g;i++)

        scanf("%d",&b[i]);

    memset(dp,0,sizeof(dp));

    dp[0][7500]=1;

    for(i=1;i<=g;i++)

        for(j=0;j<=15000;j++)

            if(dp[i-1][j])

                for(k=1;k<=c;k++)

                    dp[i][j+a[k]*b[i]]+=dp[i-1][j];

    printf("%d\n",dp[g][7500]);

}

相关文章