Vijos1025. 小飛俠的游園方案
來源：程序員人生 發布時間：2014-10-03 08:00:00 閱讀次數：2057次
試題請參見: https://vijos.org/p/1025
題目概述
經過抽簽選擇, 小智將軍第一個進入考場.
菜蟲: (身上散射出華貴(?)的光芒)歡迎你, 第一位挑戰者!!
小智: ……(走到菜蟲身后, 關燈)女王陛下, 雖然我們國家現在很富裕, 但也請您不要浪費電來用這么大功率的燈泡.
菜蟲(汗): 啊啊~~愛卿所言甚是~~那么, 你的題目是……我們的情報組織探聽到敵人的重要將領――小飛俠星期天會邀他的靈兒妹妹到公園去玩. 公園里有很多娛樂項目, 可并不是每一項他們都喜歡, 所以他們對每一項都進行了“喜歡度”的評分. 因為小飛俠也是一個了不起的角色, 所以他一定會選擇在有限時間內的最好的方案. 現在要你做的就是找出在規定時間內他們選擇哪幾項不同的活動可以使其“喜歡度”之和達到最大, 據此我們就可以知道他會在哪些地方出現, 從而在那里派人看守了.
小智: (燈泡一亮)每個地方都派人看守不就行了?!
“當~~~”
菜蟲: (手執八公分直徑炒鍋, 筋)……你是白癡嗎?-_-##(都派人去看守的話我們會有多少桌三缺一?!)
輸入
第一行一個正整數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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
