01背包问题一维数组优化

发表于   |   分类于   |  

题目大意

　　http://acm.hdu.edu.cn/showproblem.php?pid=2602

　　0-1背包问题，本题的练习主要体会01背包的存储优化，由二维数组降至一维数组，因为每次dp[i][j]总是依赖于dp[i-1][x]因此不需要将所有dp[i][j]的所有值都保存下来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 1005
int dp[MAX_SIZE];
int value[MAX_SIZE];
int volume[MAX_SIZE];
int main() {
    int T;
    scanf("%d", &T);
    for(int t = 0; t < T; t++) {
        int N, V;
        scanf("%d%d", &N, &V);
        for(int i = 1; i <= N; i++) {
            scanf("%d", &value[i]);
        }
        for(int i = 1; i <= N; i++) {
            scanf("%d", &volume[i]);
        }
        memset(dp, 0, sizeof(dp));
        //i >= 1
        for(int i = 1; i <= N; i++) {
            for(int j = V; j >= volume[i]; j--) { //注意从大到小遍历
                int a = dp[j];
                int b = dp[j - volume[i]] + value[i];
                dp[j] = a > b ? a : b;
            }
           
        }
        printf("%d\n", dp[V]);
    }
    return 0;
}

　　注意此行for(int j = V; j >= volume[i]; j--)一定要从V往小值的方向遍历，因为我们每次需要依赖上次保存的dp值，并且更新dp值，a和b的右侧dp值均是上次循环的dp值。如果for循环j从小值往大的方向遍历，那么小的dp[j]的值先会被更新，那么大的j的值对应的dp值在更新时，如果依赖于下标小的dp值时，就不是上次循环的dp值，因此要从大往小遍历。