【t060】可怜的波特
2023-09-14 09:03:46 时间
Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
哈里波特在姨夫家遭受非人待遇，他被迫做很多事。有一次，姨夫有给了他一大堆家务。哈里知道每件做完家务的时间，重要程度，还知道总时间与任务总数，他必须尽量合理的安排使他在规定时间内完成的重要程度最大。
【输入格式】
第一行，t，m(t,m<=10000)表示哈里波特的时间和姨夫要他做的家务数。
接下来m行，每行2个值表示该任务所须的时间与重要度（均小于5000）。
【输出格式】
一行di表示完成的任务重要数总和。
Sample Input
70 3 71 100 69 1 1 2
Sample Output
3
【题解】
还能有更裸的0/1背包吗？逆序枚举时间。最后输出f[m]。做得我要吐血了。
【代码】
#include <cstdio>
int m,n,w[10010],c[10010],f[10010];
int main()
{
//freopen("F:\\rush.txt","r",stdin);
scanf("%d%d",&m,&n); //输入时间上限和物品个数
for (int i = 1;i <= n;i++) //输入n个物品的信息
scanf("%d%d",&w[i],&c[i]);
for (int i = 1;i <= n;i++) //进行0/1背包操作
for (int j = m;j >= w[i];j--)
if(f[j] < f[j-w[i]] + c[i])
f[j] = f[j-w[i]] + c[i];
printf("%d",f[m]); //最后输出所用时间不超过m的最大价值度
return 0;
}