以下文章来源于小K算法 ，作者小K算法
小K算法 .
曾就职华为和美团，中山大学数学与计算机系本科，专注分享数学、算法、科学等硬核知识
来自公众号：小K算法
装不下第i个物品，则f[i][j]=f[i-1][j]
能装下第i个物品，则f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i])
int f[101][1001], w[101], v[101];
int n, m;
int main() {
cin >> m >> n;
for (int i = 1; i <= m; ++i) {
cin >> w[i] >> v[i];
}
f[0][0] = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
f[i][j] = f[i - 1][j];
if (j >= w[i]) {
f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
}
}
}
cout << f[m][n] << endl;
return 0;
}
文章首发平台：微信公众号【小K算法】。
网友评论已有0条评论, 我也要评论