算法第三次作业

算法第三次作业

时间限制 1000 ms
内存限制 128 MB

题目描述：

经过抽签选择，小智将军第一个进入考场。
　　菜虫：（身上散射出华贵（?）的光芒）欢迎你，第一位挑战者！！
　　小智：……（走到菜虫身后，关灯）女王陛下，虽然我们国家现在很富裕，但也请您不要浪费电来用这么大功率的灯泡。
　　菜虫（汗）：啊啊爱卿所言甚是那么，你的题目是……我们的情报组织探听到敌人的重要将领——小飞侠星期天会邀他的灵儿妹妹到公园去玩。公园里有很多娱乐项目，可并不是每一项他们都喜欢，所以他们对每一项都进行了“喜欢度”的评分。因为小飞侠也是一个了不起的角色，所以他一定会选择在有限时间内的最好的方案。现在要你做的就是找出在规定时间内他们选择哪几项不同的活动可以使其“喜欢度”之和达到最大，据此我们就可以知道他会在哪些地方出现，从而在那里派人看守了。
　　小智：（灯泡一亮）每个地方都派人看守不就行了？！
　　“当~~~”
　　菜虫：（手执八公分直径炒锅，筋）……你是白痴吗？-_-##（都派人去看守的话我们会有多少桌三缺一？！）听好了，输入格式是第一行一个正整数N（1< =N< =100）表示总共的娱乐项目数；第二行一个正整数表示规定的时间t（0< t< 1000）；下面有N行，其中第i+2行有两个正整数fi（0< =fi< =100）和ti（0< ti< =100），分别表示对项目i的“喜欢度”和它所耗费的时间。输出的时候在第一行输出最大的“喜欢度”之和，下面给你一个样例：

输入数据
输出数据
样例输入

3
5
1 2
5 5
4 3

样例输出

5

属于动态规划入门题，了解过0-1背包的可以一遍过。
简单介绍一下：0-1背包。
我们只有一个背包，有N种物品，包的容量为C。
对于N种物品，我们进行遍历，第i种物品的重量是Wi，价值是Vi。每种物品要么装要么不装，不存在装一部分的现象。
很显然我们对于N种物品，要找出最优解。即，找出累计价值最大的几种物品。

思路：定义二维数组M[N][C]。 //M[i][j]表示在面对第i种物品时，背包的容量为j时，所能获取到的最大价值。
从以下两方面考虑：

1、j<Wi
第i种物品的重量是Wi，当当前物品的重量大于背包现在的容量时，我们没办法放进去。
所以M[i][j] = M[i-1][j]
//M[i][j] = M[i-1][j] 表示 面对第i种物品时，它能获取到的最大价值就是在容量为j时，存放上一种物品的最大价值（即最优解）

2、j>=Wi
当第i种物品可以放到容量为j的空间里的时候，我们可以再选择，放or不放。
不放：和1、同理，M[i][j] = M[i-1][j]
放：M[i][j] = M[i-1][j-Wi]+Vi
//M[i][j] = M[i-1][j-Wi]+Vi 表示 我们把第i种物品放入我们的背包时，获取到的最大价值。
M[i-1]表示上一次添加物品时已经存在的最大价值，[j-Wi] 则表示我的当前容量减去第i种物品的容量。
综合起来，可以说M[i-1][j-Wi]表示i-1件物品时、背包容量为j-Wi时的最大价值。
加上当前第i种物品的价值Vi，即M[i][j]。
那我们要不要放着不拿？
我们要告诉计算机，请选择这两个中能有最大价值的。
即max(M[i-1][j],M[i-1][j-Wi]+Vi)

所以：

if(j<Wi)M[i][j]=M[i-1][j];
elseM[i][j]=max(M[i-1][j],M[i-1][j-Wi]+Vi);  

本题解法：

# include <stdio.h>int f[1000];int main(void)
{int n,T;scanf("%d",&n);scanf("%d",&T);int w,t;int i,j;for(i=1;i<=n;i++){scanf("%d%d",&w,&t);for(j=T;j>=t;j--){f[j]=(f[j]>f[j-t]+w)?f[j]:(f[j-t]+w);  //因为C语言不支持max函数，所以就用了三元表达式?:}}printf("%d",f[T]);return 0;
}

三元表达式

A？B:C //意思是A这个条件表达式为真吗？是，执行B，否，执行C

总结：
关于0-1背包的一些例题大家可以去网上找，看懂了基本原理，其他的都是以此为延伸。
最后放上这个题的一个在线答题网址。大家自己跑通了可以去上面试试能不能AC。
算法刚开始大部分人都不懂，主要还是看自己后面的理解和刷题了。
关于刷题网站，可以是 leetcode、杭电oj、牛客网、洛谷、vijos。
刚开始可以一边做入门的、简单的，一边看《剑指offer》了解一些基本的东西。
算法还是要好好看看的，不仅是打开大厂offer的必背，想央企国企啥的，研究生推免也会用到。
刚开始别着急。多刷题。不会就看题解，看懂流程控制，看懂每个语句的功能，试数。
（最后祝大家昨天1024程序员节快乐！）