855学习记录算法动态规划$Day$-$1$——炎泽汐$de$ Blog

01 背包

---

//01 背包
void z_o_bag(int n, int m, int w[], int v[]){
    int DP[n + 1][m + 1];
    memset(DP, 0, sizeof(DP));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            DP[i][j] = DP[i - 1][j];
            if(j >= v[i]){
                DP[i][j] = max(DP[i][j], DP[i - 1][j - v[i]] + w[i]);
            }
        }
    }
}

//01 背包状态压缩
 void z_o_bag_plus(int n, int m, int w[], int v[]){
    int DP[m + 1];
    memset(DP, 0, sizeof(DP));
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= v[i]; j--){
            DP[j] = max(DP[j], DP[j - v[i]] + w[i]);
        }
    }
}

完全背包

---

//完全背包
void CompleteBag(int n, int m, int w[], int v[]){
    int DP[n + 1][m + 1];
    memset(DP, 0, sizeof(DP));
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            for(int k = 0; k * v[i] <= j; k++){
                DP[i][j] = max(DP[i][j], DP[i - 1][j - v[i] * k] + w[i] * k);
            }
        }
    }
}

//完全背包减项优化 
void CompleteBag(int n, int m, int w[], int v[]){
    int DP[n + 1][m + 1];
    memset(DP, 0, sizeof(DP));
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            DP[i][j] = DP[i - 1][j];
            if(j >= v[i]){
                DP[i][j] = max(DP[i][j], DP[i][j - v[i]] + w[i]);
            }
        }
    }
}

//完全背包状态压缩 
void CompleteBag(int n, int m, int w[], int v[]){
    int DP[m + 1];
    memset(DP, 0, sizeof(DP));
    for(int i = 1; i <= n; i++){
        for(int j = v[i]; j <= m; j++){
            DP[j] = max(DP[j], DP[j - v[i]] + w[i]);
        }
    }
}

多重背包

---

//多重背包
void MultipleBag(int n, int m, int w[], int v[], int s[]){
    int DP[n + 1][m + 1];
    memset(DP, 0, sizeof(DP));
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            for(int k = 0; k <= s[i] && k * v[i] <= j; k++){
                DP[i][j] = max(DP[i][j], DP[i - 1][j - v[i] * k] + w[i] * k);
            }
        }
    }
}

//多重背包二进制优化 
void MultipleBag(int n, int m, int w[], int v[], int s[]){
    int ww[10 * n], vv[10 * n];
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        int k = 1;
        while(k <= s[i]){
            cnt++;
            vv[cnt] = v[i] * k;
            ww[cnt] = w[i] * k;
            s[i] -= k;
            k *= 2;
        }
        if(s[i] > 0){
            cnt++;
            vv[cnt] = v[i] * s[i];
            ww[cnt] = w[i] * s[i];
        }
    }
	
    n = cnt;
    int DP[cnt + 1];
    memset(DP, 0, sizeof(DP));
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= v[i]; j--){
            DP[j] = max(DP[j], DP[j - vv[i]] + ww[i]);
        }
    }
}

分组背包

---

//分组背包 
void GroupBag(int n, int m, int w[][100], int v[][100], int s[]){
    int DP[m + 1];
    memset(DP, 0, sizeof(DP));
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= 0; j--){
            for(int k = 0; k <= s[i]; k++){
                if(v[i][j] <= j){
                    DP[j] = max(DP[j], DP[j - v[i][k]] + w[i][k]);
                }
            }
        }
    }
}