动态规划--背包问题

01背包-每件物品一件

dp[i] [j]:从前i件物品中选，背包容量为j时，能装下的最大价值

    ...
    int dp[n+1][bagV+1];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=bagV;j++){
            if(j<w[i]){
                dp[i][j]=dp[i-1][j];
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            }
        }
    }

完全背包-每件物品无限件

dp[i] [j] :从前i件物品中选，第i件物品选k件，背包容量为j时，能装下的最大价值

    ...
    int dp[n+1][bagV+1];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=bagV;j++){
            for(int k=0;k<=j/w[i];k++){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]*k]+v[i]*k);
            }
        }  
    }

多重背包-每件物品件数有各自的上限

dp[i] [j]:从前i件物品中选，第i件物品选k件，背包容量为j时，能装下的最大价值

    ...
    int dp[n+1][bagV+1];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=bagV;j++){
            for(int k=0;k<=p[i]&&k*w[i]<=j;k++){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]*k]+v[i]*k);
            }    
        }
    }