1.状态压缩dp

2.背包

最简单的背包

void dp1(){
    for(int i=1;i<=M;i++){
        for(int j=0;j<=T;j++){
            dp[i][j]=dp[i-1][j];
            if(j-c[i]>=0) {
                dp[i][j] = max(dp[i][j],dp[i - 1][j - c[i]] + w[i]);
            }
        }
    }
    cout<<dp[M][T]<<endl;
}

优化空间复杂度的背包

void dp2() {
    for (int i = 1; i <= M; i++) {
        for (int j = 0; j <= T; j++) {
            dp[1][j] = dp[0][j];
            if (j - c[i] >= 0) {
                dp[1][j] = max(dp[1][j], dp[0][j - c[i]] + w[i]);
            }
        }
    }
}

01背包

应该对？凭印象写的

void dp3(){
    for(int i=1;i<=M;i++){
        for(int j=T;j>=0;j--){
            if(j-c[i]>=0){
                dp[j]=dp[j-c[i]]+w[i];
            }
        }
    }
}