0-1背包问题思想的算法题目

0-1背包问题思想的算法题目2015-02-11

题目概述

经过抽签选择, 小智将军第一个进入考场.

菜虫: （身上散射出华贵（？）的光芒）欢迎你, 第一位挑战者！！

小智: ……（走到菜虫身后, 关灯）女王陛下, 虽然我们国家现在很富裕, 但也请您不要浪费电来用这么大功率的灯泡.

菜虫（汗）: 啊啊~~爱卿所言甚是~~那么, 你的题目是……我们的情报组织探听到敌人的重要将领——小飞侠星期天会邀他的灵儿妹妹到公园去玩. 公园里有很多娱乐项目, 可并不是每一项他们都喜欢, 所以他们对每一项都进行了“喜欢度”的评分. 因为小飞侠也是一个了不起的角色, 所以他一定会选择在有限时间内的最好的方案. 现在要你做的就是找出在规定时间内他们选择哪几项不同的活动可以使其“喜欢度”之和达到最大, 据此我们就可以知道他会在哪些地方出现, 从而在那里派人看守了.

小智: （灯泡一亮）每个地方都派人看守不就行了？！

“当~~~”

菜虫: （手执八公分直径炒锅, 筋）……你是白痴吗？-_-##（都派人去看守的话我们会有多少桌三缺一？！）

输入

第一行一个正整数N（1<=N<=100）表示总共的娱乐项目数; 第二行一个正整数表示规定的时间t（0<t<1000）; 下面有N行，其中第i+2行有两个正整数fi（0<=fi<=100）和ti（0<ti<=100）, 分别表示对项目i的“喜欢度”和它所耗费的时间.

输出

最大的“喜欢度”之和.

解题思路

我的第一反应是回溯, 然后就TLE了 - -|||

其实这是非常典型的0-1背包问题, 然后就按照0-1背包问题的思想求解就好.

遇到的问题

一开始用回溯, 虽然我剪枝（最优性剪枝）了, 可依旧大半的测试点超时.

用0-1背包问题思想求解的时候, 第0行和第0列需要预留空白（0）, 否则当计算第一个值的时候会数组下标越界.

源代码

#include <iostream>#include <fstream>const int MAX_PROJECTS = 101;const int MAX_TIME = 1001;struct Project {int happiness;int time;Project（） {this->happiness = 0;this->time = 0;}};Project projects[MAX_PROJECTS];int values[MAX_PROJECTS][MAX_TIME];int getMaxHappiness（int totalProjects, int totalTime） {for （ int i = 1; i <= totalProjects; ++ i ） {for （ int j = 0; j <= totalTime; ++ j ） {if （ j >= projects[i].time ） {values[i][j] = std::max（values[i - 1][j], values[i - 1][j - projects[i].time] + projects[i].happiness）;} else {values[i][j] = values[i - 1][j];}}}return values[totalProjects][totalTime];}int main（） {using std::cin;// std::ifstream cin;// cin.open（"input.txt"）;int n = 0, t = 0;cin >> n >> t;for （ int i = 1; i <= n; ++ i ） {cin >> projects[i].happiness >> projects[i].time;}int maxHappiness = getMaxHappiness（n, t）;std::cout << maxHappiness << std::endl;return 0;}