回退背包专题

P4141 消失之物

题目意思，就是说有n个物品，然后每个物品都有自己的体积w[i]，然后问你，如果第i个物品丢了之后，还能够装满这个背包的方法，然后遍历一遍i同时也要遍历一遍背包，因为背包的值是在1到m之间的任意值，对于同一个物品丢失，中间结果不需要用加空格隔开，就是连在一起

题解：

这是一个回退背包问题

首先第一步，我们把正常的背包（就是正常情况下装满容积为x的背包的物品的情况的数量）求出来，然后就是板子，求出填满当中体积有多少种方法

第二步就是回退，

回退的关键问题有两个：

1. 回退的点该怎么找
2. 只把由当前物品组成的情况删除

解决这两个问题就是会了回退

这两个关键点分两步解决：

1. 当前背包容量小于我需要回退的物品时，说明我当前压根没有带走该物体，所以当前的刚好填满的方法数量还是不变

2. 当我背包容量大于等于我需要回退的物品时，说明我当前正好可以填满的方法中有部分方法是由本该退回的物品组成的，至少为1（因为当前背包容量等于当前物品体积的时候，这是肯定为一种情况的

这里对f[j]=(dp[j]-f[j-w[i]]+10)%10;解释一下

原方法总数-由退回物品组成的方法总数
为什么f[j-w[i]]是退回物品的方法总数呢？
因为w[i]与j-w[i]才能恰好组成j也就是当前背包容量，一件w[i]与n件j-w[i]可以恰好组成n种方法
还有个问题，其实我一开始在思考这里回退j-a[i]的时候会不会把之前已经回退过的二次回退导致答案变小呢
事实是不会的，完全多想
因为每次只考虑一个物品所以不搭边，因为这里的关系是关联关系，j-a[i]的方法总数是影响a[i]的方法总数，所以这边就算收到影响也是因为j-a[i]受到了影响，那么j-a[i]受到影响这个方法总数肯定是会受到影响的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int w[2005];
int dp[2005];//填满容量为j的背包的方案总数 ,dp表示原来n件物品的背包
int f[2005];//f表示拿掉第i件的背包恰好填满的情况 
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>w[i];
	dp[0]=1;
	
	//01背包
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=w[i];j--)
		{
			dp[j]=(dp[j]+dp[j-w[i]])%10;
		}
	} 
	
	for(int i=1;i<=n;i++)
	{
		f[0]=1;
		for(int j=1;j<=m;j++)
		{
			if(w[i]>j)
			f[j]=dp[j]%10;
			else
			f[j]=(dp[j]-f[j-w[i]]+10)%10;
			cout<<f[j];
		}
		cout<<"\n";
	}
	return 0;
}