链接：http://hihocoder.com/problemset/problem/1038?sid=469496
accept代码：
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4
5 int dp[501][100001];
6 int need[501];
7 int value[501];
8
9 int main()
10 {
11 int num,amount;
12 cin>>num>>amount;
13 for(int i=1;i<=num;i++)
14 {
15 cin>>need[i]>>value[i];
16 }
17
18 for(int j=1;j<=num;j++)
19 {
20 for(int i=0;i<=amount;i++)
21 {
22 if(i<need[j])
23 {
24 dp[j][i]=dp[j-1][i];
25 }
26 else
27 {
28 dp[j][i]=max(dp[j-1][i],(dp[j-1][i-need[j]]+value[j]));
29 }
30 }
31 }
32
33 cout<<dp[num][amount]<<endl;
34 return 0;
35 }
TLE代码：
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4
5 int dp[100001][501];
6 int need[501];
7 int value[501];
8
9 int main()
10 {
11 int num,amount;
12 cin>>num>>amount;
13 for(int i=1;i<=num;i++)
14 {
15 cin>>need[i]>>value[i];
16 }
17
18 for(int j=1;j<=num;j++)
19 {
20 for(int i=0;i<=amount;i++)
21 {
22 if(need[j]>i)
23 {
24 dp[i][j]=dp[i][j-1];
25 }
26 else
27 {
28 dp[i][j]=max(dp[i][j-1],(dp[i-need[j]][j-1]+value[j]));
29 }
30 }
31 }
32
33 cout<<dp[amount][num]<<endl;
34 return 0;
35 }
两段代码的唯一区别就是二维数组定义的顺序：dp[物品数][背包容量]——dp[背包容量][物品数]。
为什么呢？