问题定义

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
即在01背包基础上加上每件物品可以选任意件的条件

思路

• 状态+属性定义: f[i,j]表示前i个物品,拿总体积不超过j的所有选法中价值最大的选法.
• 状态计算:对于每一个i物品,把选法集合划分为{拿0件物品,拿1件物品,拿2件物品…拿m件物品}
  1. 拿0件i物品等于不拿,f[i,j] = f[i-1,j]
  2. 拿k件i物品等于去掉k个i物品体积的最大价值+kw[i],即f[i,j] = f[i-1,j-kv[i]]+w[i]
• 状态转移优化:查看状态方程中的冗余项
  • f[i,j] = Max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,f[i-1,j-3v]+3w…)
  • f[i,j-v] = Max(       f[i-1,j-v]+w,f[i-1,j-2v]+w,f[i-1,j-3v]+2w…)
  • 由上方程,f[i,j-v]的最大值+w是f[i,j]第一项后面所有项的最大值
  • 故f[i,j] = Max(f[i-1,j],f[i,j-v]+w)

详细代码

/*
 * @Author: ACCXavier
 * @Date: 2021-04-26 14:48:50
 * @LastEditTime: 2021-04-26 15:18:10
 * Bilibili:https://space.bilibili.com/7469540
 * 题目地址:https://www.acwing.com/problem/content/3/
 * @keywords: 完全背包问题
有 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
* 思路:属性为MAX,
* f[i,j]表示前i个物品不超过j体积的最大价值,状态划分为对第i个物品拿0~m个
* 转移方程f[i,j]=f[i-1,j-v[i]*k]+w[i]
优化:
  f[i,j] = Max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,f[i-1,j-3v]+3w…)
  f[i,j-v] = Max(       f[i-1,j-v]+w,f[i-1,j-2v]+w,f[i-1,j-3v]+2w…)
* 故f[i,j] = Max(f[i-1,j],f[i,j-v]+w)

样例模拟
首先f数组初始化全为0：给定物品种类有4种，包最大体积为5，数据来源于题目的输入
v[1] = 1, w[1] = 2
v[2] = 2, w[2] = 4
v[3] = 3, w[3] = 4
v[4] = 4, w[4] = 5

i = 1 时： j从v[1]到5
f[1] = max(f[1],f[0]+w[1]) = w[1] = 2 (用了一件物品1）
f[2] = max(f[2],f[1]+w[1]) = w[1] + w[1] = 4（用了两件物品1）
f[3] = max(f[3],f[2]+w[1]) = w[1] + w[1] + w[1] = 6（用了三件物品1）
f[4] = max(f[4],f[3]+w[1]) = w[1] + w[1] + w[1] + w[1] = 8（用了四件物品1）
f[5] = max(f[3],f[2]+w[1]) = w[1] + w[1] + w[1] + w[1] + w[1] = 10（用了五件物品）

i = 2 时：j从v[2]到5
f[2] = max(f[2],f[0]+w[2]) = w[1] + w[1] = w[2] =  4（用了两件物品1或者一件物品2）
f[3] = max(f[3],f[1]+w[2]) = 3 * w[1] = w[1] + w[2] =  6（用了三件物品1，或者一件物品1和一件物品2）
f[4] = max(f[4],f[2]+w[2]) = 4 * w[1] = f[2] + w[2] =  8（用了四件物品1或者，两件物品1和一件物品2或两件物品2）
f[5] = max(f[5],f[3]+w[2]) = 5 * w[1] = f[3] + w[2] =  10（用了五件物品1或者，一件物品1和两件物品2(f[3]已经确定)）

i = 3时：j从v[3]到5
f[3] = max(f[3],f[0]+w[3]) = f[3] = 6 //$ 保持第二轮的状态 
f[4] = max(f[4],f[1]+w[3]) = f[4] = 8 //$ 保持第二轮的状态 
f[5] = max(f[5],f[2]+w[3]) = f[4] = 10//$ 保持第二轮的状态

i = 4时：j从v[4]到5
f[4] = max(f[4],f[0]+w[4]) = f[4] = 10 //$ 保持第三轮的状态
f[5] = max(f[5],f[1]+w[4]) = f[5] = 10 //$ 保持第三轮的状态

 */
#include <iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N];
int main() {
    int n,m;
    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 = v[i]; j <= m; j++) {
            f[j] = max(f[j],f[j-v[i]]+w[i]); 
        }
    }
    cout<<f[m]<<endl;

    return 0;
}

补充笔记