借用杭电饭卡问题来浅析 01背包问题空间复杂度的优化

Problem Description

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

Input

多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。

Output

对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。

Sample Input

     1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0 
   

Sample Output

     -45 32 
   

这是一道典型的01背包问题，只不过在上面又附加了一个限制条件（如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）），但最终问的问题还是回归到了01背包问题（问最少可使卡上的余额为多少），那怎么考虑这个问题呢？

我先给一组数据按自己原始的想法去做就会有大致的思路：

菜的数量：5 菜的价格分别为： 4,7,18,7,12 饭卡上的余额： 20

好了，现在要让你买菜使得饭卡上的余额最少。我说一下我的思路，根据限制条件我先扣除来最少5（虽然到时候剩余的不一定是5快，但肯定要比5快多）块钱，让他去买最贵的那道菜（18块钱的那道），然后剩余的余额和剩余的菜进行01背包，最后是这样买的：扣除5快后，卡上余额15,怎么买呢？7+7=14这就是最好的选择了（还剩余1块），最后5+1=6，去买最贵的那道菜6-18=-12。最终答案就是-12.

和原始01背包问题的区别：

（1）这里饭卡01背包问题和物品装到背包里面有个小小的区别就是物品装背包告诉了物品的价值和质量，而这里没告诉你质量，仔细一想就会发现，背包把物品装进去走之后就会把物品的质量减掉，这里一样的效果，买完菜就把菜价扣除掉，相对于物品放背包，你可以把菜价看成，即是菜的价值也是菜的质量，再把余额看成背包容量

（2）还有就是，这里不需要知道你到底买了那几道菜，所以不用去寻找x[i]的值了

接着上篇博文，先看一下我一开始的代码

#include "iostream"
#include "math.h"
#include "algorithm"
using namespace std;

int main()
{
	int a[1005],m[100][100],x[1005],n,sum,i,j,c;
	memset(a,0,sizeof(a));
	while(scanf("%d",&n)!=EOF&&n!=0)
	{
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	
	sort(a+1,a+n+1);
	cin>>c;
	memset(m,0,sizeof(m));
	if(c < 5)
	{
        printf("%d\n",c);
	}
	else
	{
        for(i = 1; i <= n-1; i++)  
	{
               for( j = 0; j <=c-5; j++)  
		{
                   m[i][j] = m[i-1][j];
		   if(j>=a[i])
		   {
                    m[i][j] = m[i-1][j] > m[i-1][j-a[i]] + a[i]? m[i-1][j] : m[i-1][j-a[i]] + a[i]; 
		   }
		}
	}
	    sum=c-m[n-1][c-5]-a[n];
	    cout<<sum<<endl;
	}
	}
}

注意这里一开始我的m二维数组是这样的m[1005][1005]结果运行之后是这样

后来才知道是二维数组的问题，

秒客网

借用杭电饭卡问题来浅析 01背包问题空间复杂度的优化

相关文章