01背包（定义）
2026-01-03 12:00:50
发布于：四川
1.1 核心描述
给定 n 件物品（重量 w[i]，价值 v[i]）和容量 m 的背包，选物品使总重量≤m且总价值最大。
状态定义： 二维：dp[i][j] 表示前 i 件物品、容量 j 的最大价值； 一维（优化）：dp[j] 表示容量 j 的最大价值（需反向迭代避免重复选）。
1.2 核心代码
1.2.1 基础二维版
1.2.1.1 四要素分析
状态：dp[i][j]表示考虑前i件物品、背包容量为j时的最大价值（二维状态覆盖“物品数量”和“背包容量”两个维度）。
转移： 若j < w[i]（容量不足，无法选第i件物品），则dp[i][j] = dp[i-1][j]（继承前i-1件物品的状态）； 若j ≥ w[i]（容量足够，可选或不选），则dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（不选则继承，选则加v[i]并扣减重量）。
边界：dp[0][j] = 0（前0件物品，价值为0）、dp[i][0] = 0（容量为0，无法装物品，价值为0）。 答案：dp[n][m]（考虑所有n件物品、容量为m时的最大价值）。
void packsack(){//01背包：二维数组实现
//dp[到哪个物品][到哪个容量] = 前i件物品、容量j的最大价值（状态定义）
for(int i=1;i<=n;i++){//遍历物品
for(int j=0;j<=m;j++){//遍历容量
if(j<w[i]) dp[i][j]=dp[i-1][j];//容量不足，无法选第i件，继承前一状态（转移1）
else//容量足够，选或不选取最大值（转移2）
dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
}
}
cout<<dp[n][m];//输出前n件物品、容量m的最大价值（答案）
}
1.2.2 一维优化版（反向迭代）
1.2.2.1.1 四要素分析
状态：dp[j]表示背包容量为j时的最大价值（压缩为一维，通过迭代顺序保证“前i件物品”的逻辑）。
转移：对每件物品i，反向遍历容量j=m~w[i]，则dp[j] = max(dp[j], dp[j-w[i]] + v[i])（反向迭代避免同一物品被重复选择，确保dp[j-w[i]]是前i-1件物品的状态）。
边界：dp[j] = 0（初始所有容量的价值为0，无物品时价值为0）。
答案：dp[m]（容量为m时的最大价值）。
void packsack_optimize(){//01背包：一维数组反向迭代
cin>>n>>m;
memset(dp,0,sizeof dp); // 边界初始化
for(int i=1;i<=n;i++){//遍历物品
// 反向迭代：避免同一物品被重复选择（保证状态转移正确性）
for(int j=m;j>=w[i];--j){
dp[j]=max(dp[j], dp[j-w[i]]+v[i]); // 状态转移
}
}
cout<<dp[m]<<endl; // 答案
}
这里空空如也
有帮助，赞一个