完全背包问题（空间优化，打印路径）

完全背包问题的详细介绍这里不再赘述，仅给出代码模板。其中代码中的文字包含了三种类型的完全背包问题的求解思路以及路径打印。

​
//HDU1114
//写在前面：这里给出HDU1114题作为样例
//完全背包问题：有N种物品，每i种物品的体积为vc[i]，价值为w[i],数量不限
//有一容量为C的背包，问如何装能使背包的体积最大
//当使用二维数组时的状态转移方程为：dp[i][v]=max(dp[i-1][v],dp[i][v-vc[i]]+w[i])
//空间优化后的状态转移方程变为：dp[v]=max(dp[v],dp[v-vc[i]+w[i])
//这里又分为装满和不装满问题；这时dp数组的初始化将会有差别
//不装满是dp数组全为0，dp[0]=0;装满时dp=inf(inf为极大值或极小值）dp[0]=0; 
#include <iostream>
#include <string.h>
#define maxn 505
#define inf 0x3f3f3f3f
using namespace std;
int p[maxn];int w[maxn];
int dp[10005];
int path[maxn][10005];//打印路径数组 
int min(int a,int b)
{
	if(a<b)return a;
	else return b;
}
int main()
{
	int t;cin>>t;
	while(t--)
	{
		int E,F;cin>>E>>F;
		int n;cin>>n;
		for(int i=0;i<n;i++)cin>>p[i]>>w[i];
		memset(dp,inf,sizeof(dp));dp[0]=0;
		memset(path,0,sizeof(path)); 
		//若求最大的情况则变为：memset(dp,-inf,sizeof(dp));dp[0]=0; 
		for(int i=0;i<n;i++)
		{
			for(int j=w[i];j<=F-E;j++)
			{
				if(dp[j]>dp[j-w[i]]+p[i])
				{
					dp[j]=dp[j-w[i]]+p[i];
					path[i][j]=1;//将该物品放入路径中 
				}
			}
		}
		if(dp[F-E]!=inf)cout<<\"The minimum amount of money in the piggy-bank is \"<<dp[F-E]<<\'.\';
		else cout<<\"This is impossible.\";
		cout<<\'\\n\';
		//需要打印路径的话可以将48-59行的代码加上去 
/*		cout<<\"the path is: \";
		int i=n-1;int j=F-E;
		while(i>=0&&j>=0)
		{
			if(path[i][j])
			{
				cout<<p[i]<<\' \';
				j-=w[i];
			}
			else i--;
		}
		cout<<\'\\n\';*/
	}
}
/*
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
*/

​