动态规划思想(1)

背包问题

​ 分类：

01 背包问题

​

• 含义：每个物体最多选1次，在不超过总体积的情况下价值最大
• 图解：

• f(i,j)表示的是集合的某种属性，是个值。

• 集合是所有选法

• i 只从前i个中选

• 朴素实现

  #include
  #includeusing namespace std;const int N = 1010;int n,m;//n代表物品个数m代表容量
  int v[N],w[M];//v代表体积，w代表价值
  int f[N][N];//全局变量默认为0int mian(){cin >> n >> m;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];//for[0][0~m]//考虑0件物品，最大价值不超过0~m  但默认为0所以可以不写for(int i = 1; i <= n; i++)for（int j = 0; j <= m; j++）{//j代表体积f[i][j] = f[i-1][j]//代表左边不含i的情况if(j >= v[i])//如果第i件物品体积大于背包就装不下了f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]);}cout << f[n][m] << endl;return 0;
  }
  

  • 一维实现

    
    #include
    #includeusing namespace std;const int N = 1010;int n,m;//n代表物品个数m代表容量
    int v[N],w[M];//v代表体积，w代表价值
    int f[N];//全局变量默认为0int 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;
    }
    

• 滚动数组：如果f()只用到了上层的数据，完全可以只用f(2)和f(1)交替来算。不需要创建额外的空间。

• 一维实现：运用了滚动数组的思想，每次找最大值就是从前面一次的数组寻值，而且由于公式的原因不可能从原地址取值。运用了一维就可以直接把前面i代表的那一维去掉

02完全背包问题

• 朴素实现

  #include
  #includeusing namespace std;const int N = 1010;int n,m;
  int v[N],W[N];
  int f[N][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 - v[i]*k] + w[i] * k);cout << f[n][m] << endl;}
  

  优化思路：

• 代码

  #include
  #includeusing namespace std;const int N = 1010;int n,m;
  int v[N],W[N];
  int f[N][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 << f[n][m] << endl;}
  

• 和01背包问题比较，可以看出还能继续优化

#include
#includeusing 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 = v[i]; j <= m; j++)f[i][j] = max(f[j],f[j-v[i]] + w[i]);cout << f[m] << endl;}

; i <= n; i++) cin >> v[i] >> w[i];

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

}

- 01背包问题从小到大，完全背包是从大到小。为什么01和完全只差个顺序呢？