2016级算法期末上机-A.简单·Bamboo's Fight with DDLs I

简单·Bamboo's Fight with DDLs I

分析

一句话：要装满的完全背包问题。
对比完全背包只有一点要改变：初始化为负无穷
传送门: https://buaacoding.cn/problem/101/index 装满的01背包，有何不同大家自己思考

代码样例

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxx = 400;
const int INF = -10000000;
int dp[maxx];
struct todo
{
	int d, h;
}TD[375];
int main()
{
	int n, m;
	while (~scanf("%d%d", &n, &m))
	{
		memset(dp, INF, sizeof(dp));
		for (int i = 0; i < n; i++)
			scanf("%d%d", &TD[i].d, &TD[i].h);
		dp[0] = 0;
		for (int i = 0; i < n; i++)
			for (int j = TD[i].d; j <= m; j++)
				if (dp[j] < dp[j - TD[i].d] + TD[i].h)
					dp[j] = dp[j - TD[i].d] + TD[i].h;
		if (dp[m] > 0)printf("%d
", dp[m]);
		else printf("!
");
	}

}

数据

由于后期数据问题，导致有初始化不是负无穷的同学一直没过，会适当补偿