acwing 2. 01背包问题

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。第 i件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且价值最大。输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000

0<vi,wi≤1000

输入样例

4 5

1 2

2 4

3 4

4 5

输出：

8

思路：动态规划

1.状态表示f[i,j]——(1)集合：所有只考虑前i个物品，且总体积不大于j的所有选法; (2)属性：Max

2.状态计算——集合的划分

朴素做法：

//动态规划：分解为求子问题的最优解//相关链接：/qq_38410730/article/details/81667885?utm_source=app// /problem/content/2/#include <iostream>using namespace std;const int N = 1010;int f[N][N]; //状态表示：集合f[i][j]——前i个物品且总体积不大于j的最大价值（C++全局变量会初始化为0）int w[N],v[N]; //体积 和 价值int main(){int n,m;cin>>n>>m; //物品总数量，背包总容积for (int i = 1; i <= n; ++i) {cin>>v[i]>>w[i]; //第i件物品的体积和价值}//f[0][0] 已经自动为0了，不用再写了//下面可以理解成打表for (int i = 1; i <= n ; ++i) { //装的件数for (int j = 0; j <= m; ++j) {//最大容量//第一个类型：不含i的集合——f(i-1,j) 当前背包的容量不够，为前i-1个物品最优解//第二个类型：含i的集合——f(i-1,j-vi)+wi) 当前背包容量够，选与第i个物品//求两边的最大值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]); //先减去第i个，并减去他的质量，再加上i的价值}}}cout<<f[n][m]<<endl;return 0;}

优化

//思路和上面的一致#include<iostream>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=m;j>=v[i];j--){ //在这里是从后往前，这样就可以保证取到的是上一次未更新位置的值，即i-1时候的值f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];}