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\n", dp[m]);
        else printf("!\n");
    }

}

数据

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