背包问题

? ! 白白！？

2026-08-27 11:57:05

发布于：上海

9阅读

0回复

0点赞

背包DP

动态规划的经典应用-背包问题。
一般来说，就是给定一组有固定价值和固定重量的物品，以及一个承重量固定的背包，求在不超过背包最大承重的前提下，能放进背包里的物品的最大总价值。
动态规划（DP）类问题主要求解的步骤
1、划分阶段
2、确定状态
3、确定决策并写出转移方程式
贪心为什么错？
根本原因：贪心需要算性价比（单位重量的价值），但题中的物品不可分割，所以计算性价比来排序的策略是错的。
所以，可以考虑01搜索，对每个物品遍历“选 or 不选”两种情况，但是可能会超时。

背包问题分类：01背包，完全背包，多重背包，分组背包……

1. 01背包
问题定义：有 n 件物品和一个容量为 v 的背包，第i件物品体积 wi ，价值 vi ，每件物品只有一件，只能选或不选，求不超过容量的前提下能获得的最大总价值

状态定义：

dp[i][j] 表示前 i 个物品，容量为 j 时的最大价值

状态转移：

选第 i 件物品且容量够，则 dp[i][j] = dp[i - 1][j - w[i]] + v[i]
不选第 i 件物品，则 dp[i][j] = dp[i - 1][j]
dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])

答案：

一般来说，dp[n][m];

实现代码：

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