暴力解法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N]; // f[i][j] 表示只考虑前i个物品,且总体积不大于j的所有选法
int v[N], w[N];
int 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 = 1 ; j <= m ; j ++)
for (int k = 0 ; k * v[i] <= j ; k ++)
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
cout << f[n][m] << endl;
return 0;
}
时间复杂度优化
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N]; // f[i][j] 表示只考虑前i个物品,且总体积不大于j的所有选法
int v[N], w[N];
int 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 = 1 ; j <= m ; j ++)
f[i][j] = max(f[i - 1][j], j >= v[i] ? f[i][j - v[i]] + w[i] : 0);
cout << f[n][m] << endl;
return 0;
}
状态压缩
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N];
int v[N], w[N];
int 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 = v[i] ; j <= m ; j ++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
/**
* 1. 01背包: f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w)
* 2. 完全背包:f[i][j] = max(f[i - 1][j], f[i][j - v] + w)
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
int v, w;
cin >> v >> w;
for (int j = 1; j <= m; j ++)
{
f[i][j] = f[i - 1][j];
if (j >= v)
f[i][j] = max(f[i][j], f[i][j - v] + w);
}
}
cout << f[n][m] << endl;
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
int v, w;
cin >> v >> w;
for (int j = 1; j <= m; j ++)
if (j >= v)
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}