01背包_顺序枚举和逆序枚举的问题_一维数组

 1 #include  2 #include  3 #include  4 using namespace std;
 5 const int M=1e5+10;
 6 int w[M],v[M];
 7 int n,m;
 8 int dp[M];
 9 
10 int T;
11 void check(int i,int j) {
12 
13     cout"容量为""的背包中,""放入第""个物品\n";
14     printf("容量: ");
15     for(int k=1; k) {
16         cout" ";
17     }
18     printf("\n价值: ");
19     for(int k=1; k) {
20         cout" ";
21     }
22     puts("\n\n");
23 }
24 /*
25 3 5
26 3 5 2 6 4 10
27 
28 */
29 void f1() {
30     memset(dp,0,sizeof(dp));
31     //dp[j]=max(dp[j],dp[j-w[i]]+v[i]);i(1,n),j>=w[i],
32     //容量初始值j=m
33     //决策时i为常数， 所以 i 在最外层
34     for(int i=1; i) {
35         /*
36         for(int j=m; j>=w[i]; j--) { //
37             dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
38         }*/
39         for(int j=1; j) {
40             if(j>=w[i])dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
41             check(i,j);
42         }
43     }
44     coutendl;
45 }
46 void f2() {
47     memset(dp,0,sizeof(dp));
48     //dp[j]=max(dp[j],dp[j-w[i]]+v[i]);i(1,n),j>=w[i],
49     //容量初始值j=m
50     //决策时i为常数， 所以 i 在最外层
51     for(int i=1; i) {
52 
53         for(int j=m; j>=w[i]; j--) { //
54             dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
55             check(i,j);
56         }
57 
58     }
59     coutendl;
60 }
61 /*
62 5 1000
63 144 990
64 487 436
65 210 673
66 567 58
67 1056 897
68 
69 2099
70 */
71 int main() {
72 
73     cin>>n>>m;
74     for(int i=1; i>w[i]>>v[i];
75     f1();
76     system("pause");
77     f2();
78 
79     return 0;
80 }