每周学习总结：第八周。

本周学习：动态规划背包问题（四种类型：一、01背包；二、完全背包；三、多重背包；四、分组的背包问题。）(三四 下周总结。)

一 、 01背包；

（物品选不选，物品只能用一次。）
问题描述：有N件物品和一个容量为V的背包。第i件物品的费用（即体积，下同）是w[i]，价值是val[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

解题思路：用动态规划的思路，阶段就是“物品的件数”，状态就是“背包剩下的容量”，那么很显然dp[ i , v ] 就设为从前 i 件物品中选择放入容量为 v 的背包最大的价值。那么状态转移方程为：

dp[i][v]=max（ dp[i-1][v],dp[i-1][v-w[i]]+val[i] ）。

这个方程可以如下解释：只考虑子问题“将前 i 个物品放入容量为 v 的背包中的最大价值”那么考虑如果不放入 i ，最大价值就和 i 无关，就是 dp[ i - 1 ][ v ] , 如果放入第 i 个物品，价值就是 dp[ i - 1][ v - w[i] ] + val[ i ]，我们只需取最大值即可。
优化思想：
需要用计算顺序来保证当计算dp[i][j]时，dp[j-k]中存储的都是i-1时的值。
直接修改代码，发现dp[j-k]会被第i次计算覆盖。
所以让j从大到小计算，可以保证dp[j-k]保存着上一轮计算的值不被覆盖。
部分代码：

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

所以解题代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e4;
int dp[maxn];
int w[maxn],val[maxn];
void solve(int n,int m)
{
	memset(dp,0,sizeof (dp));
	for(int i = 1;i <= n;i++)
	{
		for(int v = m;v > 0;v--)
		{
			if(v >= w[i])
				dp[v] = max(dp[v],dp[v-w[i]]+val[i]);
		}
	}
	printf("%d\n",dp[m]);
}
int main(){
	int n,m;
	while(scanf("%d%d",&n,&m) != EOF){
		for(int i = 1;i <= n;i++) scanf("%d%d",w+i,val+i);
		solve(n,m);
	}
	return 0;
}

二、完全背包。

（物品无限选）。
问题描述：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是val[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

解题思路：完全背包问题与0/1背包问题不同之处在于其每个物品是无限的，从每种物品的角度考虑，与它相关的策略就变成了取0件、1件、2件…。我们可以根据0/1背包的思路，对状态转移方程进行改进，令f[i][v]表示前 i 种物品恰放入一个容量为 v 的背包的最大权值。状态转移方程就变成了：
f[i][v]=max(f[i-1][v],f[i][v-w[i]]+val[i])

我们通过对0/1背包的思路加以改进，就得到了完全背包的一种解法，这种解法时间复杂度为O（n^3）， 空间复杂度 为O （n^2）。

时间优化：根据上述f[ i ][ v ]的定义，其为前 i 种物品恰好放入容量为 v 的背包的最大权值。根据上述状态转移方程可知，我们假设的是子结果f[ i-1 ][ v-k*w[i] ]中并没有选入第 i 种物品，所以我们需要逆序遍历（像0/1背包一样）来确保该前提；但是我们现在考虑“加选一件第 i 种物品”这种策略时，正需要一个可能已经选入第 i 种物品的子结果f[ i ][ v-w[i] ]，于是当我们顺序遍历时，就刚好达到该要求。这种做法，使我们省去了一层循环，即第 i 种物品放入的件数k，从而时间复杂度优化为O（n^2）。

空间优化：正如0/1背包的空间优化，上述状态转移方程已经优化为：
f[i][v]=max(f[i-1][v],f[i][v-w[i]]+val[i])

将这个方程用一维数组实现，便得到了如下伪代码：

for i = 1..N

　　　for v = 0..V

　　　　 f[v] = max(f[v],f[v-w[i]] + val[ i ] );

计算顺序：从小到大。在计算第i个物品时，f[j]中存储的数据不需要为第i-1个物品的情况，因为物品i可以取多个。所以f[j]的意义变为了前i个物品任意取，体积为j的最大价值。取i-1和取i个物品的情况共同竞争体积为j的f[j]。

感想：
能力有限 ，目前就学了这两种。
1、 动态规划的状态转移方程是与所确定状态紧密联系的，因此要写出方程，还应仔细思考状态可能有哪些情况。

总而言之，动态规划，是利用抽象的思维来解决问题的，处理动态规划问题时，一定要找准状态（重要），通过严密的思维和逻辑推导出方程，并处理好边界的状态。
下周目标：
1、每天1~2题， 周末 2~3 题 。