背包问题

#include <iostream>

using namespace std;
const int MAX=100;
int dp[MAX][MAX];
int w[MAX],v[MAX];
int n,W;
//正序
void slove(){
    for(int i=0;i<n;i++){
        for(int j=0;j<=W;j++){
            if(j<w[i]){
                dp[i+1][j] = dp[i][j];
            }else{
                dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);
            }
        }
    }
    cout<<dp[n][W]<<endl;
}
//倒序
void slove1(){
    int i,j;
    for(i=n-1;i>=0;i--){
        for(j=0;j<=W;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]);
            }
        }
    }
    cout<<dp[0][W]<<endl;
}
int main()
{
    cin>>n>>W;
    for(int k=0;k<n;k++)
        cin>>w[k]>>v[k];
    //slove();
    slove1();

    return 0;
}

完全背包：

#include <iostream>

using namespace std;
/**
    完全背包推导：
    dp[i+1][j] = max(dp[i][j-k*w[i]]+k*v[i],k>=0)
        dp[i+1][j] = max(dp[i][j],dp[i][j-k*w[i]]+k*v[i],k>=1)
        dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]-k*w[i]]+k*v[i]+v[i],k>=0)
        dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
*/
const int MAX = 100;
int n,W;
int dp[MAX][MAX];
int w[MAX],v[MAX];

void slove(){
    int i,j;
    for(i=0;i<n;i++){
        for(j=0;j<=W;j++){
            if(j<w[i])
                dp[i+1][j] = dp[i][j];
            else
                dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
        }
    }
    cout<<dp[n][W]<<endl;
}
int main()
{
    cin>>n>>W;
    for(int k=0;k<n;k++)
        cin>>w[k]>>v[k];
    slove();

    return 0;
}

int dp[MAX];
/*
01背包
void slove1(){
    int i,j;
    for(i=0;i<n;i++){
        for(j=W;j>=w[i];j--){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout<<dp[W]<<endl;
}
*/
void slove1(){
    //完全背包 不需要考虑dp[i+1]状态 只是从重量的角度出发
    int i,j;
    for(i=0;i<n;i++){
        for(j=w[i];j<=W;j++){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout<<dp[W]<<endl;
}