XTU-OJ-1436-礼物-笔记

参考博客

xtuoj 1436 礼物（01背包板子题

题意

输入两个数字，第一个数字是商品数量，第二个数字是有的钱数，然后输入商品的价格，开心度和不开心度，买下某件商品，加上开心度，不买某件商品，减去开心度

数据范围

商品数量在16以内，钱数在1000以内，两个数字同时为0表示输入结束

价格在200以内

开心度和不开心度都在50以内

输入

3 100
30 10 5
80 20 16
60 15 7
3 100
30 10 5
70 20 16
60 15 6
0 0

输出

9
24

代码

#include<stdio.h>
#include<string.h>

#define N 20

int a[N],b[N],c[N];
int dp[N][1010];

int maxx(int a,int b)
{
	int ans=0;
	if(a>b)	ans=a;
	else	ans=b;
	
	return ans;
}

int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0)
		{
			break;
		}
		
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d",&a[i],&b[i],&c[i]);
		}
		
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=m;j++)
			{
				if(j<a[i])	dp[i][j]=dp[i-1][j]-c[i];
				else dp[i][j]=maxx(dp[i-1][j-a[i]]+b[i],dp[i-1][j]-c[i]);
			}
		}
		
		int ans=-1e9;
		for(int i=0;i<=m;i++)
		{
			ans=maxx(ans,dp[n][i]);
		}
		
		printf("%d\n",ans);
		
		memset(dp,0,sizeof dp);
		memset(a,0,sizeof a);
		memset(b,0,sizeof b);
		memset(c,0,sizeof c);
	}
	
	return 0;
}

想法

用 const c语言编译错误

然后是这个是枚举专题里面的，为啥用的是dp来求解

虽然是简单的dp，但是我还是不会写，属于01背包问题，到底怎么才能会写呢？

枚举出来好像也不难，可能还是得慢慢来吧……

答案的最小值取0还会WA，这是为啥，啥都买不起答案会为负数

枚举商品件数，枚举价格（类似于背包的容积），然后建立状态转移方程，第一维表示的是商品数目，第二维表示的是价格，dp的数值表示的是开心度的大小，最后要求的是最大的开心度

表示购买该件商品就把价格减去，然后加上开心度，不购买的话就把价格不变，减去不开心度