题目描述

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N, V <= 1000
0< vi, wi <=1000

样例

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

二维

一、状态表示 (f[i][j])

集合：表示从前i种中选取，总体积小于等于j

属性：最大值Max

状态计算

第i种一件也装不下，f[i][j] = f[i - 1][j] （该条件永远成立）

第i种装k件，f[i][j] = f[i - 1][j - k * v[i]] + j * w[i] （k = 1, 2, 3 …）

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 1010;
int f[N][N];
int v[N], w[N];
int n, m;

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            for(int k = 1; k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }
    cout << f[n][m] << '\n';
    return 0;
}

优化为一维

见y总视频推出的公式

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-2*v]+2*w , .....)
可得： f[i][j]=max(f[i,j-v]+w , f[i][j])

从而可优化掉k的循环

for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j];
            if(j - v[i] >= 0)f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }

形式与01背包惊人的相似，故按01背包优化方法即可优化为一维
由于此处为f[i][j - v[i]]，故j从小到大进行遍历即可
代码如下

for(int i = 1; i <= n; i ++ )
        for(int j = v[i]; j <= m; j ++ ) 
            f[j] = max(f[j], f[j - v[i]] + w[i]);