A deformation of 0-1 knapsack problem, submitted several times are wrong,,, solve the ah,,
Here is the topic link http://coder.buct.edu.cn/JudgeOnline/problem.php? Id=1981

Title description
Chen is a gifted child, his dream is to become the world's most the great physician, to that end, he want to close to the most prestigious physician for the teacher, physicians in order to judge his qualifications, poses a conundrum for him, doctor took him to a cave is full of herbs and said to him: "children, the cave has some different herbs, each plant needs some time, each one has its own value, I'll give you a period of time, during this time, you can pick some herbal medicine, if you are a clever boy, you should be able to make to the total value of herbal medicine is the largest," if you are Chen, can you accomplish this task?

Enter
Input file medic. In the first line has two integer T (1 & lt;=T & lt;=1000) and M (1 & lt;=M & lt;=100), separated by a space, T represents the total time can be used to herbalism, M number of herbal medicines in the cave, the next M lines of each row consists of two between 1 to 100 (including integers, 1 and 100) respectively to pick a time and the value of this plant herbal plant herb,

O
Output file medic. Out including a line, the line contains only one integer, within the prescribed period of time, can adopt to the maximum value of herbs,

The sample input
70
71, 100,
69 1
1
2Sample output
3
Tip
About 30% of the data, M & lt;=10; For all of the data, M & lt;=100,

This is my code, solution to what is going wrong

#include
#include
using namespace std;

# define MAXM 110
# define MAXT 1010
Int Weight;
The int Value.
Int T, M;
Int f [MAXM] [MAXT];

Void GetAnswer ()
{
for(int i=1; I<=M; I++)
{
Cin> Weight> The Value;
for(int j=0; j<=T; J++)
If (j>=Weight)
{
If (f [I - 1) [j] & gt; [j] [I f - 1 - Weight] + Value)
[I] [j] f=f [I - 1] [j];
The else
[I] [j] f=f [j - Weight] [I - 1] + Value;
}
}
}

Int main ()
{
//freopen (" test. TXT ", "r", stdin);
//freopen (" *. TXT ", "w", stdout);
Cin> T> M;
Memset (f 0, sizeof (f));
();
Coutreturn 0;
}

CodePudding user response:

This is my review of 0-1 knapsack problem such as variant of parsing,
http://blog.csdn.net/tbwood/article/details/22728109