虽然01背包时间复杂度几乎无法再优化，但我们可以优化空间复杂度，也就是把f数组压成一维的 那么我们现在如何用一维数组f[0...j]得到？ 事实上，我们只需要将v倒推即可，不过与无优化的不同的是，由于我们把f[i]定义为不超过v公斤的最大价值，那么我们要把v推到从w[i]即可，之后由于放不进去了，所以我们无需继续循环 那么此时状态转移方程为f[i]=max(f[i],f[v-w[i]]) (v>=w[i],i:1-n)

#include<bits/stdc++.h>
using namespace std;
int dp[1001],w[1000],v[1001];
int main()
{
	int m,n; 
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&w[i],&v[i]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=w[i];j--)//dp表示重量不超过j的最大价值 
		{
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//状态转移方程其实等效于01背包，只不过变了形式 
		}
	}
	cout<<dp[m];
	return 0;
}

那个……由于更新时间过长，所以这两篇表述时的数组或变量名可能与我的程序不符qwq

w[i]是体积，c[i]是价值 用f[i][j]定义当第i件物品时背包容量为j时的最优解 那么最终答案就是f[n][m] 那么当第i件物品能被放入空间为j时的背包中时 f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i])（i:1-n,j:m-1） 如果第i件物品放不到容量为j的背包中时，我们直接考虑继承，即f[i][j]=f[i-1][v]; 那么我们的状态转移方程就出来了，如上 那么程序也就解决啦~

#include<bits/stdc++.h>
using namespace std;
int dp[1001][1001];//用来存储第i件物品，背包空间为j的最大值 
int w[1001],v[1001];//重量+价值 
int main()
{
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&w[i],&v[i]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=1;j--)//倒推 
		{
			if(w[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//如果能放得下，就有两种选择：1，不放，此时f[i][j]=f[i-1][j](前一件的状态）2，放，那么放下去之后背包所剩空间等于j-w[i],f[i][j]=f[i-1][j-w[i]];综上，dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) 
			else dp[i][j]=dp[i-1][j];//如果放不下就没得选喽，只能是前一件的状态了 
		}
	}
	cout<<dp[n][m];//输出最优 
	return 0;
}