Coins(背包方案数+物品数量维护)

COINS

题意：

多组输入$nm$（0 0 时退出）
每个物品的价值 每个物品的数量
问最多能凑出几种不同的金额？

思路：

输入
开一个数组$f[i]$来看这个值有没有被凑到过，然后我们使每次都使要凑的值是没有被凑到过的，然后进行标记。然后因为它物品的数量是有限制的，所以还要维护每个物品的数量上限，三重循环肯定会超时，那么我们要怎么维护呢？难点就在于此。我们对于每个物品开一个数组$ff$，通过状态转移，如果当前数值可以被凑出来，那么说明当前数值用了一个硬币，那么它应该是几个硬币呢，就看它上一个状态是什么，上一个状态是$ff[j?v[i]]$，也就是说上次用了$ff[j?v[i]]$，那么也就是说这次用了$ff[j?v[i]]+1$个硬币，为了防止串联，所以对于每个物品的$ff$数组，我们使$ff$初始化都为$0$；每新增一个面值标记，就使答案$+1$，最后输出答案即可。

//三重循环超时版╰（‵□′）╯╰（‵□′）╯╰（‵□′）╯╰（‵□′）╯╰（‵□′）╯╰（‵□′）╯╰（‵□′）╯
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
//#define int long long
using namespace std;const int N = 100010;signed main()
{
    int n, m;int f[N], v[N], s[N];int ff[N];while (cin >> n >> m){
    if (n == 0 && m == 0) break;for (int i = 1; i <= n; i ++ ) cin >> v[i];for (int i = 1; i <= n; i ++ ) cin >> s[i];memset(f, -1, sizeof f);f[0] = 1;int ans = 0;for (int i = 1; i <= n; i ++ ){
    for (int k = 1; k <= s[i]; k ++ ){
    memcpy(ff, f, sizeof f);for (int j = v[i]; j <= m ; j ++ ){
    if (ff[j - v[i]] != -1 && ff[j] == -1) //原本这里写的是v[i] * k，这就错了。。。应该是用一个物品的体积 {
    ans ++;f[j] ++;}}}}cout << ans << endl;}return 0;
}

//正解v??????ヾ(≧▽≦*)oヾ(≧▽≦*)oヾ(≧▽≦*)oヾ(≧▽≦*)oヾ(≧▽≦*)o
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N], v[N], c[N], ff[N];
int main()
{
    int n, m;while (cin >> n >> m){
    if (n == 0 && m == 0) break;
// memset(v, 0, sizeof v);for (int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);memset(f, 0, sizeof f);f[0] = 1;int ans = 0;for (int i = 1; i <= n; i ++ ){
    
// cout << v[i] << ": ";memset(ff, 0, sizeof ff); //初始化数组for (int j = v[i]; j <= m; j ++ ){
    //判断当前值没有被凑到过，上一个状态存在，且数量够用if (!f[j] && f[j - v[i]] && ff[j - v[i]] < c[i]){
    
// cout << j << " ";f[j] = 1;ff[j] = ff[j - v[i]] + 1;ans ++;}}
// cout << endl;}cout << ans << endl;}return 0;
}