题目描述
01 背包 i表示放入第多少个 (前面i-1的放置)j的最大重量(j>v[i])才可以防止
f[i][j]=max(f[i][j],f[i-1][j-v[i]+w[i])//表示前面i-1种防止后为满足达到j重量就要减去第i个物品的重量,再与不放做比较取最大值
(背包01 )
算法1二维
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N], w[N], f[N][N];
int main()
{
int n, m;
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 - 1][j - v[i]] +w[i]);
}
}
cout << f[n][m];
return 0;
}
算法2 一维
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N], w[N], f[N];
int main()
{
int n, m;
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 = m; j >=v[i]; j--)//从后往前保证前面的j没有被更新过
{
f[j] = max(f[j], f[j - v[i]] +w[i]);
}
}
cout << f[m];
return 0;
}