hdu1147-完全背包&&hdu2191-多重背包

历尽千辛万苦 终于把完全背包弄明白了，由此可鉴，对于动态规划的子结构 还是不太熟悉。加油！！！吖飒 相信自己！我可以的。。。

题意：

选择硬币使瓶子满(W)，且value最小。

看懂题就知道 是个完全背包问题。

对于完全背包，

二维解法：

假定dp[i][j],i代表放置了i个硬币重量是j。子结构就是dp[i-1][j-w[j]]+p[j](少放一个硬币，重量是当前重量减该硬币的重量)，

dp[i][w]中最小的值即为解。

由于每个硬币可以放很多次，要多加一个循环，w[j]分解成(k*w[j]),p[j]分解成k*p[j]（1=<k<=W/w[j]）即每个硬币分解成很多个重量价值一样的硬币。

初始化问题，当W=0时，dp[i][0]=0;

另计：这种解法 有没有很像多重背包呢、、、、像， 很像！

一维解法：

用心观察会发现，dp[i][j-w[i]]的j-w[i]就代表着i-1的状态。dp[j]与dp[j-w[i]]的关系就对应着i与i-1的关系。即dp[j]=min(dp[j],dp[j-w[i-1]]+p[i-1]);

初始化，dp[0][0]=0;

一维解法的优化：

由于dp[i][j],i代表放置了i个硬币重量是j，i-1就是少放一个的情况，假设无论之前是否放过，即无论之前放置了几个某硬币，还可以继续放置。简化为了真正的完全背包(与0-1背包的区别就在于0-1背包只能放置一个，前面放过的不能再放所以必须n-1)

状态转移方程：dp[i]=min(dp[i],dp[i-w[i]]+p[i]);

代码：

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct info
{
	int p;
	int w;
}N[505];
int dp[10001];//物品重j
//题意是求j为某个值时是否可行，可行输出最小的value
int min(int a,int b)
{
	return a>b?b:a;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int i,j,k;
		int Min=100000000;
		scanf("%d%d",&i,&j);
		int W=j-i;
		int n;
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d%d",&N[i].p,&N[i].w);
		/*二维解法很可能超时
		for(i=0;i<=n;i++)
			for(j=1;j<=W;j++)
			{dp[i][0]=0;dp[i][j]=100000000;}
		for(i=1;i<=n;i++)
		{
			for(j=N[i-1].w;j<=W;j++)
			{
				for(k=N[i-1].w;k<=j;k+=N[i-1].w)
				{
					dp[i][j]=min(dp[i][j],dp[i-1][j-k]+k/N[i-1].w*N[i-1].p); 
					if(j==W&&Min>dp[i][j]) Min=dp[i][j];
				}
			}
		}*/
		//由二维简化成一维数组
		/*for(j=1;j<=W;j++)
			dp[j]=100000000;
		dp[0]=0;
		for(i=1;i<=n;i++)
		{
			for(j=N[i-1].w;j<=W;j++)
			{
				for(k=N[i-1].w;k<=j;k+=N[i-1].w)
				{
					dp[j]=min(dp[j],dp[j-k]+k/N[i-1].w*N[i-1].p); 
				}
			}
		}*/
		for(j=1;j<=W;j++)
			dp[j]=100000000;
		dp[0]=0;
		for(i=0;i<n;i++)
		{
			for(j=N[i].w;j<=W;j++)
				dp[j]=min(dp[j],dp[j-N[i].w]+N[i].p); 
		}
		if(dp[W]<100000000)
		printf("The minimum amount of money in the piggy-bank is %d.\n",dp[W]);
		else 
		printf("This is impossible.\n");
	}
	return 0;
}

顺势我又写了个多重背包的题，其实很像完全背包。

懂了完全背包的。。。。多重的小case(仅指该题、、、、)

题意：

不用我说的 汉语 、、、、果断不解释

详见代码吧

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct info
{
	int p;//重量
	int w;//价格
	int c;//数量
}N[105];
int dp[101][101];//放i种物品重j
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int i,j,k;int W,n;
		int Min=0;
		scanf("%d%d",&W,&n);
		for(i=0;i<n;i++)
			scanf("%d%d%d",&N[i].w,&N[i].p,&N[i].c);
		for(i=0;i<=n;i++)
			for(j=1;j<=W;j++)
			dp[i][j]=0;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=W;j++)
			{
				for(k=0;k<=N[i-1].c;k++)
				{
					if(j>=k*N[i-1].w) dp[i][j]=max(dp[i][j],dp[i-1][j-k*N[i-1].w]+k*N[i-1].p); 
					if(Min<dp[i][j]) Min=dp[i][j];
				}
			}
		}
		printf("%d\n",Min);
	}
	return 0;
}