一個關于0-1背包的問題變形，提交了好多次都是錯誤。。。求解啊。。
這里是題目鏈接http://coder.buct.edu.cn/JudgeOnline/problem.php?id=1981
題目描述
辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。” 如果你是辰辰，你能完成這個任務嗎？
輸入
輸入檔案medic.in的第一行有兩個整數T（1 < = T < = 1000）和M（1 < = M < = 100），用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞里的草藥的數目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數，分別表示采摘某株草藥的時間和這株草藥的價值。
輸出
輸出檔案medic.out包括一行，這一行只包含一個整數，表示在規定的時間內，可以采到的草藥的最大總價值。
樣例輸入
70 3
71 100
69 1
1 2
樣例輸出
3
提示
對于30%的資料，M < = 10；對于全部的資料，M < = 100。
這是我的代碼，求解哪里出問題了
#include<iostream>
#include<cstring>
using namespace std;
#define MAXM 110
#define MAXT 1010
int Weight;
int Value;
int T,M;
int f[MAXM][MAXT];
void GetAnswer()
{
for(int i=1;i<=M;i++)
{
cin>>Weight>>Value;
for(int j=0;j<=T;j++)
if(j>=Weight)
{
if(f[i-1][j]>f[i-1][j-Weight]+Value)
f[i][j]=f[i-1][j];
else
f[i][j]=f[i-1][j-Weight]+Value;
}
}
}
int main()
{
//freopen("test.txt","r",stdin);
//freopen("tested.txt","w",stdout);
cin>>T>>M;
memset(f,0,sizeof(f));
GetAnswer();
cout<<f[M][T]<<endl;
return 0;
}
uj5u.com熱心網友回復：
這是我寫的關于0-1背包的變種等問題的決議。http://blog.csdn.net/tbwood/article/details/22728109
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/123307.html
標籤：基礎類
下一篇：鏈表中的主要函式求詳細解釋？