1.3思路二介绍(一维数组) 空间优化

  为什么可以使用一维数组？

  我们先来看一看01背包问题的状态转移方程，我们可以发现 f[i]只用到了f[i-1]，其他的是没有用到的，我们可以用滚动数组来做。
  还有一个原因就是我们在计算f[i] [j]的时候我们只用到了f[i-1] [j]和f[i-1] [j-v[i]]，其中j和j-v[i]都是小于等于j的，在j的同一侧，所以我们综合以上两点原因就可以将二维优化到一维，即完成空间优化。

我们先来将二维和优化后的一维在关键算法代码上进行一下对比：

for(int i = 1; i <= n; i++) for(int j = m; j >= 0; j--){if(j < v[i]) f[i][j] = f[i - 1][j];  // 优化前f[j] = f[j];            // 优化后，该行自动成立，可省略。else    f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);  // 优化前f[j] = max(f[j], f[j - v[i]] + w[i]);                   // 优化后}

实际上，只有当枚举的背包容量 >= v[i] 时才会更新状态，因此我们可以修改循环终止条件进一步优化。

for(int i=1;j<=n;i++)
{for(int j=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);}
}

#include 
#include using namespace std;const int N = 1010;int n, m;
int v[N], w[N];
int f[N];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 = m; j >= v[i]; j -- )f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[m] << endl;return 0;
}

1.4思路三介绍(输入数据优化)

  我们注意到在处理数据时，我们是一个物品一个物品，一个一个体积的枚举。因此我们可以不必开两个数组记录体积和价值，而是边输入边处理。

#includeusing namespace std;const int MAXN = 1005;
int f[MAXN];  // int main() 
{int n, m;   cin >> n >> m;for(int i = 1; i <= n; i++) {int v, w;cin >> v >> w;      // 边输入边处理for(int j = m; j >= v; j--)f[j] = max(f[j], f[j - v] + w);}cout << f[m] << endl;return 0;
}

2.完全背包问题

2.1题目描述：

2.2思路一(朴素算法)

#include
using namespace std;
const int N=1010;
int f[N][N];
int n,m;
int v[N],w[N];
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=0;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<

for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{f[i][j] = f[i-1][j];//状态一，即不取第i个物品if(j-v[i]>=0)//判断是否可以加入第i个物品f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);//状态二
}

#include
using namespace std;
const int N=1010;
int f[N][N];
int n,m;
int v[N],w[N];
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=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i]){f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);}}}cout<

//01背包问题核心优化后代码
for(int i=1;i<=n;i++)
{for(int j=m;j>=v[i];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]);}}
}
//完全背包问题核心优化后代码
for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{f[i][j] = f[i-1][j];//状态一，即不取第i个物品if(j-v[i]>=0)//判断是否可以加入第i个物品f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);//状态二
}

for(int i = 1 ; i<=n ;i++)for(int j = v[i] ; j<=m ;j++)//注意了，这里的j是从小到大枚举，和01背包不一样{f[j] = max(f[j],f[j-v[i]]+w[i]);}

#include
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[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 = v[i] ; j<=m ;j++){f[j] = max(f[j],f[j-v[i]]+w[i]);}cout<