Coins

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

const int M = 100010;

int n, m;
int w[N], s[N];
int f[M]; // 能否拼出总面值是j
int sum[M]; // 总面值大于等于M， 至少需要多少枚硬币

int main() {
    while (cin >> n >> m) {
        if (n == 0 && m == 0)
            break;
        memset(f, 0, sizeof f);
        memset(sum, 0, sizeof sum);

        for (int i = 1; i <= n; i ++ )

            cin >> w[i];

        for (int i = 1; i <= n; i ++ )

            cin >> s[i];
        int ans = 0;
        f[0] = 1;

        for (int i = 1; i <= n; i ++ ) {

            memset(sum, 0, sizeof sum);

            for (int j = w[i]; j <= m; j ++ ) {

                if (sum[j - w[i]] < s[i] && f[j] == 0 && f[j - w[i]] == 1) {
                    f[j] = 1;
                    sum[j] = sum[j - w[i]] + 1;
                    ans ++ ;
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}

完全背包

优化

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

const int M = 1e5 + 10;

int n, m;
int w[N], v[N];
int f[M];

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )

        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )

        for (int j = v[i]; j <= m; j ++ )

            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}

朴素

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

const int M = 1e5 + 10;

int n, m;
int w[N], v[N];
int f[N][M];

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )

        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )

        for (int j = 0; j <= m; j ++ ) {

            f[i][j] = f[i - 1][j];

            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;
    return 0;
}

采药

朴素

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

const int M = 1010;

int n, m;
int w[N], v[N];
int f[N][M];

int main() {
    cin >> m >> n;

    for (int i = 1; i <= n; i ++ )

        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )

        for (int j = 0; j <= m; j ++ ) {

            f[i][j] = f[i - 1][j];

            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;
    return 0;
}

优化

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

const int M = 1010;

int n, m;
int w[N], v[N];
int f[M];

int main() {
    cin >> m >> n;

    for (int i = 1; i <= n; i ++ )

        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )

        for (int j = m; j >= v[i]; j -- )

            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}

寒冰王座

朴素

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int M = 10010;

int n, m;
int w[] = {0, 150, 200, 350};
int f[4][M];

int main() {
    int t;
    cin >> t;

    while (t -- ) {
        cin >> m;
        memset(f, 0, sizeof f);

        for (int i = 1; i <= 3; i ++ )

            for (int j = 0; j <= m; j ++ ) {

                f[i][j] = f[i - 1][j];

                if (j >= w[i])
                    f[i][j] = max(f[i][j], f[i][j - w[i]] + w[i]);
            }

        cout << m - f[3][m] << endl;
    }

    return 0;
}

优化

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int M = 10010;

int n, m;
int w[] = {0, 150, 200, 350};
int f[M];

int main() {
    int t;
    cin >> t;

    while (t -- ) {
        cin >> m;
        memset(f, 0, sizeof f);

        for (int i = 1; i <= 3; i ++ )

            for (int j = w[i]; j <= m; j ++ )

                f[j] = max(f[j], f[j - w[i]] + w[i]);


        cout << m - f[m] << endl;
    }

    return 0;
}