题目描述
算法1
C++ 代码
#include<bits/stdc++.h>
using namespace std;
// Tag: 多重背包 记录种类数
//这个nt写法会超时!
/*
状态表示:
f[i][j] 表示 j 能否由前 i 种物品拼成
属性:可能性
状态转移:
对于最后一个物品 i ,面值为 wi, 数量为 ci
f[i][j] = f[i-1][j-k*wi] (k<=ci && k*wi<=j)
然后,在最后一维度,遍历所有的 j ,如果为1,则说明可以组成,cnt++。
*/
/*
这样写肯定会超时,得考虑其他的状态表示。
状态表示:
f[i,j]表示前i钟硬币能够组成的状态种类数
属性:数量
状态转移:
*/
const int N=110, M=1e5+10;
int f[N][M];
int n,m;
int a[M],c[M];
int main()
{
while(scanf("%d %d",&n,&m),n+m)
{
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
memset(f,0,sizeof f);
for(int i=0;i<=c[1] && i*a[1]<=m;i++) f[1][i*a[1]]=1;
for(int i=1;i<=n;i++) f[i][0]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j] = f[i-1][j];
if(f[i][j]==0)
for(int k=1;k<=c[i] && k*a[i]<=j;k++)
{
if(f[i-1][j-k*a[i]]==1)
{
f[i][j]=1;
break;
}
}
}
}
int ans=0;
for(int i=1;i<=m;i++)
{
if(f[n][i]==1) ans++;
}
cout<<ans<<endl;
}
return 0;
}
算法2
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
/*
上一种写法一定会超时的。
1. 每次都要重复赋值, 因为f[i][j]只能赋值0,1,而且一旦赋值为1
之后,就不可能赋值为0,所以,前一种写法的 浪费了很大时间来重复
给同一最终状态赋值。
2. 对于同一 j 来说,第一种写法需要 再遍历 k 次,看其中是否有
能够拼成的。这没有利用好条件。
j从小到大遍历,所以说,在i这一唯,不需要每个都判j次,如果上一个
j-v[i]它不能拼成,现在的和以后的都不能拼成。
*/
const int N = 110, M = 100010;
int n, m;
int f[M], g[M];
int v[N], s[N];
int main()
{
while (scanf("%d%d", &n, &m), n || m)
{
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);
for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
f[0] = 1;
for (int i = 1; i <= n; i ++ )
{
memset(g, 0, sizeof g);
for (int j = v[i]; j <= m; j ++ )
if (!f[j] && f[j - v[i]] && g[j - v[i]] < s[i])
{
g[j] = g[j - v[i]] + 1;
f[j] = 1;
}
}
int res = 0;
for (int i = 1; i <= m; i ++ ) res += f[i];
printf("%d\n", res);
}
return 0;
}
dl的更多写法:
(题解和题解里的评论)
https://www.acwing.com/solution/content/11075/