题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000

输入样例

5 18
3 1
4 2
6 7
5 3
1 2

输出样例

14

解题思路

背包状态表示:f[j] 表示拿体积不超过j的物体能达到的最大价值
状态转移方程:f[j] = max(f[j],f[j-v[i]]+w[i]) 其中i为每一个物体
解释:对于特定一个物体i而言,f[j]的值有两种情况,从两种情况中挑出最大的
1.不拿i,f[j]不变
2.拿i,那么最大价值F就是(i的价值w[i])+(拿i后剩余的体积能找到的最大价值),拿 i后剩下体积为j-v[i],所以剩下体积的最大价值为f[j-v[i]], 于是最大价值=f[j-v[i]]+w[i]
故状态方程为f[j] = max(f[j],f[j-v[i]]+w[i])

详细代码注释和样例模拟:

/*
 * @Author: ACCXavier
 * @Date: 2021-04-25 19:57:50
 * @LastEditTime: 2021-04-25 20:43:21
 * Bilibili:https://space.bilibili.com/7469540
 * 题目地址:https://www.acwing.com/problem/content/2/
 * @keywords: 01背包
*/
/*!!!!!!!!!!!!!!!!!!!
5 18
3 1
4 2
6 7
5 3
1 2
模拟样例 v=18 下标从1开始
    体积v 价值w
1物品: 3   1
2物品: 4   2
3物品: 6   7
4物品: 5   3
5物品: 1   2

第一个物体表示为1: 更新的时候只说明更改的值,未修改的值按上
1:f(18)~f(3)=1 ,f(2)~f(1)=0;
2:f(18)~f(7)=3 ,f(6)~f(4)=2,f(3)=1;f(2)~f(1)=0;
3:f(18)~f(13)=1+2+7=10;
  f(12)=max(3,f(12-v[3])+w[3])=max(3,f(6)+7) = 9
  f(9) = 8,f(7)=max(3,f(1)+7)=7,f(6) = 7,f(5)~f(4)=2,f(3)=1,f(2)~f(1) = 0
4:f(18)=13;f(17) = max(10,f(17-5)+3) = 12; f(16)~f(15)=12;
  f(14)=max(10,f(14-5)+3)=11;....
5:f(18) = max(13,f(17)+2)=14

f(m)由比m小的转移过来  没问题
*/
#include <iostream>
using namespace std;
const int N = 2020;
int f[N];//状态
int v[N],//volume 体积
    w[N];//worth 价值
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 0; i < n; ++ i){
        scanf("%d%d",&v[i],&w[i]);
    }

    for(int i = 0;i < n; ++ i){
        for(int j = m; j >= v[i]; --j){
/*我们只有上一层dp值的一维数组，更新dp值只能原地滚动更改；
注意到，当我们更新索引值较大的dp值时，需要用到索引值较小的上一层dp值dp[j - v[i]]；
也就是说，在更新索引值较大的dp值之前，索引值较小的上一层dp值必须还在，还没被更新；
所以只能索引从大到小更新。
*/
            f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;

    return 0;
}