完全背包dp优化

01背包：每个物品只能选择一次
状态转移方程
$f[i][j]=max(f[i][j],f[i-1][j-v]+w)$f[i][j]=max(f[i][j],f[i−1][j−v]+w)

完全背包：每个物品可以选择无数次

状态转移方程
$f[i][j]=max(f[i][j],f[i][j-v]+w)$f[i][j]=max(f[i][j],f[i][j−v]+w)
其中v表示第i个物品的体积，w表示第i个物品的价值

状态表示
集合：从前i个物品中选，体积不超过j
属性：最大值max
$\Rightarrow f[i][j]$⇒f[i][j]表示只从前i个物品中选，并且体积不超过j的方案的最大价值。
状态计算
对于$f[i][j]$f[i][j],划分集合，可以划分为很多个
对于第i个物品，我们不选,对应的最大价值:$f[i-1][j]$f[i−1][j]
对于第i个物品，我们只选1个,对应的最大价值：$f[i-1][j-v]+w$f[i−1][j−v]+w
对于第i个物品，我们只选2个,对应的最大价值：$f[i-1][j-2v]+2w$f[i−1][j−2v]+2w
不失一般性，选择k个，对应的最大价值:$f[i-1][j-kv]+kw$f[i−1][j−kv]+kw
只要不超过背包容量m的限制，可以一直选择下去，假设最多放k件物品。
所以，状态计算的方程为上述计算结果的最大值：
$f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,...,f[i-1][j-kv]+kw,)（1）$f[i][j]=max(f[i−1][j],f[i−1][j−v]+w,f[i−1][j−2v]+2w,...,f[i−1][j−kv]+kw,)（1）

使用变量代换：令j=j-v,此时$f[i][j-v]$f[i][j−v]表示只在前i个物品中选，背包容量不超过j-v的方案的价值最大值。
有
$f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w,...,f[i-1][j-kv]+(k-1)w,)$f[i][j−v]=max(f[i−1][j−v],f[i−1][j−2v]+w,f[i−1][j−3v]+2w,...,f[i−1][j−kv]+(k−1)w,)

这里并没有增加一项$f[i-1][j-(k+1)v]+kw$f[i−1][j−(k+1)v]+kw，这是因为背包容量从j变成了j-v，如果背包容量为j时最多可以放k件物品，那么背包容量为j-v时，背包最多可以放k-1件物品。

我们发现
即(1)式的后半部分可以使用f[i][j-v]+w来表示
所以，最后的状态转移方程为
$f[i][j]=max(f[i][j],f[i][j-v]+w)$f[i][j]=max(f[i][j],f[i][j−v]+w)
ac代码（朴素解法）

#include<iostream>
#include<cstring>
using namespace std;

const int maxn=1010;

int n,m,dp[maxn][maxn],a[maxn],v[maxn],w[maxn];
int main(){
	cin>>n>>m;//读入物品数目，背包容量
	//base case 
	memset(dp,0,sizeof(dp));//数组全部置零
	for(int i=1;i<=n;i++){//从1开始存
	
			cin>>v[i]>>w[i];//读入每件物品的体积和价值
	}
	
	for(int i=1;i<=n;i++)//状态转移
		for(int j=1;j<=m;j++){
			dp[i][j]=dp[i-1][j];
			if(j>=v[i])//背包放得下
				dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
		}
	cout<<dp[n][m]<<endl;
} 

ac代码（空间优化解法）

主要代码
dp[j-v[i]]小于dp[j],此时从小到大遍历背包容量时，dp[j-v[[i]]已经更新到本层，而不是上一层。满足//相当于dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i])
根据闫氏dp分析法， 代码更改之后需要逻辑没变，发现等价后没变。

for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			dp[j]=dp[j];//相当于dp[i][j]=dp[i-1][j]
			if(j>=v[i])
			//背包容量为j时的最大价值	
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
			//相当于dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i])
			
		}
	cout<<dp[m]<<endl;//输出背包容量为m时的结果 

这样我们就省掉了空间。

#include<iostream>
#include<cstring>
using namespace std;

const int maxn=1010;

int n,m,dp[maxn],a[maxn],v[maxn],w[maxn];
int main(){
	cin>>n>>m;
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
	
			cin>>v[i]>>w[i];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){//遍历背包容量
			if(j>=v[i])
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//背包容量为j时的最大价值	
		}
	cout<<dp[m]<<endl;//输出背包容量为m时的结果 
} 

更精简的写法
把遍历背包容量直接提到循环里面for(int j=v[i];j<=m;j++)

#include<iostream>
#include<cstring>
using namespace std;

const int maxn=1010;

int n,m,dp[maxn],a[maxn],v[maxn],w[maxn];
int main(){
	cin>>n>>m;
	memset(dp,0,sizeof(dp));
	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++){//遍历背包容量 
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//背包容量为j时的最大价值	
		}
	cout<<dp[m]<<endl;//输出背包容量为m时的结果 
} 

以后写完全背包就写优化后的解法