二维费用的背包问题

板子题
链接：https://www.acwing.com/problem/content/8/

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0 
#include 
#include 
#include 
using namespace std;
const int N = 101;
int n,V,M;
int f[N][N];
int main()
{
    cin>>n>>V>>M;
    for(int i=0;i>v>>m>>w;
        for(int j=V;j>=v;j--)//两个限制因素，分别是重量和体积
        for(int k=M;k>=m;k--)
        f[j][k]=max(f[j][k],f[j-v][k-m]+w);//状态转移
    }
    cout< 
相关题
 链接：https://www.acwing.com/problem/content/4084/
 
给定 n 个整数 a1,a2,…,an。

请你从中选取恰好 k 个数，要求选出的数的乘积的末尾 0 的数量尽可能多。

请输出末尾 0 的最大可能数量。

输入格式
第一行包含两个整数 n,k。

第二行包含 n 个整数 a1,a2,…,an。

输出格式
一个整数，表示末尾 0 的最大可能数量。

数据范围
前 6 个测试点满足 1≤n,k≤10。
所有测试点满足 1≤n≤200，1≤k≤n，1≤ai≤1018。

输入样例1：
3 2
50 4 20
输出样例1：
3
输入样例2：
5 3
15 16 3 25 9
输出样例2：
3
输入样例3：
3 3
9 77 13
输出样例3：
0
 
代码出处：https://www.acwing.com/solution/content/76935/
 在这位老哥代码的基础上，我优化了一下常数，将时间压缩到了接近两秒
 
#include 
using namespace std;



typedef long long ll;
const int N = 210, M = N * 25; //范围内一个数所包含的最多5个数为 25
//把物品这层优化掉，不然会炸空间
int f[N][M];
int v[N], w[N],sum[N];//sum为前缀和数组，存前i个数一共有多少个因数5.

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
sum[0]=0;
    for(int i = 1; i <= n; ++i)
    {
        ll a;
        scanf("%lld", &a);
        while(a % 5 == 0) a /= 5, ++v[i]; //重量
        sum[i]=v[i]+sum[i-1];//求前缀和
        while(a % 2 == 0) a /= 2, ++w[i]; //价值
    }

    //恰好 k 个
    memset(f, -0x3f, sizeof f);

    f[0][0] = 0; //初始化
    for(int i = 1; i <= n; ++i) //数字
        for(int j = min(m,i); j > 0; --j) //体积   一个数的体积默认为1，min(m,i)保证了选的个数不超过总数。
            for(int k = sum[i]; k >= v[i]; --k)  // 重量 5 数量，将k设为前i个数中因数5的总数
                f[j][k] = max(f[j][k], f[j - 1][k - v[i]] + w[i]);  //最大价值 2 的数量


    //最后遍历一遍找最大
    int ans = 0;
    for(int k = 1; k <= sum[n]; ++k)
        ans = max(ans, min(f[m][k], k)); // min(2, 5)，k表示5的个数，f[m][k]表示有k个5时，2的个数
    printf("%dn", ans);
    return 0;
}