08-28 课堂笔记0-1背包问题

Kaito

2026-08-28 17:43:33

发布于：上海

0阅读

0回复

0点赞

0-1背包问题

概念部分

定义：

    有n件物品和一个容量为v的背包。第i件武平体积为w[i]，价值为v[i]，每一件物品只有一件，只能选或者不选。
    求不超过容量的前提下能获得的最大总价值

为什么不适用贪心：

    根本原因：物品时不可以分割的吗，而性价比是算的是体积为1是的利润
    而反之如果可以分割就可以考虑贪心了，若不可分割则就是背包DP

状态设计：

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

转移方程：

如果选第i件物品，dp[i][j]=dp[i-1][j-w[i]]+v[i];（i-1表示上一行，j-w[i]表示左边的某一列，所i是从左上角来的）
如果不选第i件物品，dp[i][j]=dp[i-1][j]

二维背包模板代码

题目描述

辰辰要进山采药。山洞里有 M 株草药，采摘第 i 株需要花费 w [i]单位时间，采到后能得到 v [i]的价值。
他总共只有 T 单位时间。每株草药要么完整采下来（花掉对应的时间），要么干脆不采，不能只采一部分。
请问在时间用完之前，他最多能采到多少价值的草药？

输入格式

第一行两个整数 T 和 M，用一个空格分隔，分别表示总时间和草药数目。
接下来 M 行，每行两个整数 w [i]和 v [i]表示第 i 株草药的采摘时间和价值。

输出格式

一行一个整数，表示在规定时间内能采到的最大总价值。

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

滚动数组优化(一维DP的优化）

状态数组的空间开销与物品个数，背包容量有关，但容易空间超限。于是考虑优化空间开县，用一维数组来实现状态数组。

观察转移方程：

容易发现第i行的数值只依赖于第i-1行，既然前面的都用不上，就可以把二位压缩陈以为，反复覆盖使用

滚动数组优化代码模板：

题目描述

Bessie 要给自己的手链挑饰品。手链能承受的总重量上限是 M。
现在有 N 个候选饰品，第 i 个重 W [i]，能带来 D [i]的魅力值。每个饰品最多只能用一次。
请问在不超过重量上限的前提下，手链的魅力值总和最大是多少？

输入格式

第一行两个整数 N 和 M，分别表示饰品个数和手链的重量上限。
接下来 N 行，每行两个整数 W [i]和 D [i] ，表示第 i 个饰品的重量和魅力值。

输出格式

一行一个整数，表示能获得的最大魅力值总和。

#include<bits/stdc++.h>
using namespace std;
const int N=12885;
int dp[N];
int w[N],d[N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i]>>d[i];
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            if(j>=w[i]){
                dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
            }
            
        }
    }
    cout<<dp[m];
    return 0;
}