01 背包问题

dp[i][j] 表示前i件物品背包容量为j的情况下的最大价格

c[i] 表示第i件物品的价格

v[i] 表示第i件物品的体积

如果 v[i] <= j （第i件物品的体积<=背包容量）
  dp[i][j] = max(不拿第i件物品的最大价格，拿第i件物品的最大价格);
  dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+c[i]);
否则 （第i件物品的体积>背包容量）
  dp[i][j] = 不拿第i件物品的最大价格;
  dp[i][j] = dp[i-1][j];

01背包代码模板

#include<bits/stdc++.h>
using namespace std;
int dp[25][105],n,w;
int v[25],c[25];
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=w;j++){
            if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+c[i]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][w];
    return 0;
}

01背包代码模板（滚动数组）

#include<bits/stdc++.h>
using namespace std;
int dp[105],n,w;
int v[25],c[25];
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=w;j>=v[i];j--){
            dp[j]=max(dp[j],dp[j-v[i]]+c[i]);
        }
    }
    cout << dp[w];
    return 0;
}