文章

17

粉丝

166

获赞

6

访问

143.2k

头像
01背包变种
P1164 清华大学上机题
发布于2021年3月5日 20:32
阅读数 8.7k

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int INF = 1e9;

int a[N];
int f[N][N];
//f[i][j]前i张凑成j总值,最小的邮票数
int main()
{
    int m, n;
    while(cin >> m)
    {
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];

        //f[:][0] = 0
        //f[0][:] = INF
        //f[i][j] = min(f[i-1][j], f[i-1][j-a[i]] + 1)
        //注意初始化为inf
        memset(f, 0x3f, sizeof f);
        for(int i = 0; i <= n; i++) f[i][0] = 0;

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                f[i][j] = f[i - 1][j];
                if(j >= a[i]) f[i][j] = min(f[i][j], f[i - 1][j - a[i]] + 1);
            }

        if(f[n][m] == 0x3f3f3f3f) cout << 0 << endl;
        else cout << f[n][m] << endl;
    }
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发