所用题目

P2722

题目背景

选手在我们 USACO 的竞赛中的得分越多我们越高兴。

我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。

题目描述

我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。

你的任务是写一个程序来告诉 USACO 的职员,应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。

输入格式

输入的第一行是用空格隔开的两个整数，分别代表竞赛时间 m 和题目类 n。

第 2 到第 (n+1) 行，每行两个用空格隔开的整数，第 (i+1) 行的整数 **p_i,t_i**分别代表解决第 i 类题得到的分数和需要花费的时间。

既然是某一类题目，那么这一类题目可以重复选择。

输出格式

输出一行一个整数，代表最大的总分。

输入输出样例

输入

300 4
100 60
250 120
120 100
35 20

输出

605

说明/提示

数据规模与约定

对于 100% 的数据，保证 1≤n,m≤10⁴，1≤p_i,t_i≤10 ⁴。

第一次解题

在第一次解题时因为我最擅长的语言是Python，所以就用了Python解题，结果7/12个测试点显示了内存超限，最终只有40%的分数。

class backpack:
    def __init__(self,c,w):self.c,self.w=c,w
    def complete(self,N,C,L):
        dp=[[0]*(C+1)for i in range(N+1)]
        for i in range(1,N+1):
            for j in range(C+1):
                dp[i][j]=dp[i-1][j]
                for k in range(j//L[i].c+1):dp[i][j]=max(dp[i][j],dp[i-1][j-k*L[i].c]+k*L[i].w)
                if j>=L[i].c:dp[i][j]=max(dp[i][j],dp[i][j-L[i].c]+L[i].w)
        return dp[N][C]
m,n=map(int,input().split())
L=[0]*(1+n)
for i in range(1,1+n):
    p,t=map(int,input().split())
    L[i]=backpack(t,p)
print(L[i].complete(n,m,L))

第二次解题

后来我听说只是单纯的语言问题，所以我又打开了许久没用的C，然而结果并不理想，事实证明并非单纯的语言问题。减少了4个测试点，总共是74分，仍然有内存超限的问题。而且由于使用空间过大，不只是答题页面显示了内存超限，在编译器上运行时也出现了报错（这里的宏N原本是用于直接定义最大限的，但后来不得不改小以在编译器上运行）。

#include<stdio.h>
#define max(a,b) a>b?a:b
#define N 10001
int main()
{
    int m,n,i,j,k;
    scanf("%d%d",&m,&n);
    int p[10001]={0},t[10001]={0};
    for (i=1;i<=n;i++)
        scanf("%d%d",&p[i],&t[i]);
    int dp[10001][10001]={0};
    for (i=1;i<=n;i++)
        for(j=0;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j];
            for(k=0;k<j/t[i]+1;k++)dp[i][j]=max(dp[i][j],dp[i-1][j-k*t[i]]+k*p[i]);
            if(j>=t[i])dp[i][j]=max(dp[i][j],dp[i][j-t[i]]+p[i]);
        }
    printf("%d",dp[n][m]);
    return 0;
}

第三次解题

在答题结束后，我想起来了一个在入门书上因为对初学者有难度而基本是一笔带过的一个知识点——滚动数组。因为dp过程中，每一行实际只与上一行有关，运算永远只针对相邻两行，而且我们最终也只取最后一行数值，中间变量并不需要多余的空间存储。所以我们可以进行空间上的优化，最终免去了不必要的内存。需要注意的是，此算法并没有进行时间算法复杂度的优化。

#include<stdio.h>
#define max(a,b) a>b?a:b
#define N 1001
#define M 10001
int main()
{
    int m,n,i,j,k;
    scanf("%d%d",&m,&n);
    int p[n+1],t[n+1];
    for (i=1;i<=n;i++)
        scanf("%d%d",&p[i],&t[i]);
    int dp[m+1];
    for(j=0;j<=m;j++)
        dp[j]=0;
    for(i=1;i<=n;i++)
        for(j=0;j<=m;j++)
        {
            for(k=0;k<j/t[i]+1;k++)dp[j]=max(dp[j],dp[j-k*t[i]]+k*p[i]);
            if(j>=t[i])dp[j]=max(dp[j],dp[j-t[i]]+p[i]);
        }
    printf("%d",dp[m]);
    return 0;
}