Acwing.01背包

Acwing.01背包
🍕🎉🥓🎊🚗🐷😱❤😀❣🥙🎇🕵️‍♀️😎🎑🎁🎉😚🎇

题目：

• 有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

示例：

• 输入： 第一行两个整数，$N$，$V$，用空格隔开，分别表示物品数量和背包容积。接下来有 $N$ 行，每行两个整数 $v_i$， $w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。
• 输出： 输出一个整数，表示最大价值。
• 数据范围： $0<N,V\le 1000$ ； $0<v_i,w_i\le 1000$；

解题思路：（动规😋）

1. 确定dp数组及下标含义： dp[i][j] 表示为从前 $i$ 件物品中选，容量不超过 $j$ 的最大价值；
2. 确定递推公式： dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i])；
3. dp数组初始化： 初始化为0；
4. 确定遍历顺序： 先遍历背包 $i$ 从 $1$ 到 $n$，再遍历容量 $j$ 从 $0$ 到 $m$。

版本一：C++

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int v[N], w[N];
int dp[N][N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);
    
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++){
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    cout << dp[n][m] << endl;
    
    return 0;
}