题目描述
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N = 1e3 + 10;
int n, V;
int f[N], v[N], w[N];
int main()
{
cin >> n >> V;
for (int i = 1; i <= n; i++) scanf("%d %d", &v[i], &w[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= V; j++)
if (j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[V] << endl;
return 0;
}
样例
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N = 1e3 + 10;
int n, V, f[N][N], v[N], w[N];
int main()
{
cin >> n >> V;
for (int i = 1; i <= n; i++) scanf(“%d %d”, &v[i], &w[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= V; j++)
{
//不选第i个物品
f[i][j] = f[i - 1][j];
//选择若干个第i个物品
if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
cout << f[n][V] << endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla