本文主要是介绍c++ dp基础完全背包细讲，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 一、完全背包是什么？
- 二、使用方法
- 1.完全背包
- 2、理解
- 三、代码
- 例题
一、完全背包是什么？
一般是几种物品，一个容器，每种物品都可以无限拿，求最大价值
二、使用方法
1.完全背包
例题讲解：
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最
大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其 重量的和小于等于M
，而价值的和为最大。
输入格式:
第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)； 第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。
输出格式:
仅一行，一个数，表示最大总价值。
限制:
空间限制：128MByte
时间限制：1秒
样例:
输入：10 4
2 1
3 3
4 5
7 9
输出：
max=12
这就是一道完全背包问题的模板题，
2、理解
在上一篇博客（https://blog.csdn.net/struct_cym/article/details/118569863）中写到了刷表法，现在还是用刷表法来做，但这里就不给大家画表了，就直接来理解吧
完全背包问题中，每个物品有无限件，也就是从每种物品的角度考虑，与它相关的策略并非选或者不选两种。而是：选0件、选1件、选2件…等等多种策略。
现在我们可以借用0/1背包问题的策略，把每一种情况的的结果都计算出来，再找到最大者，存在dp数组里
转移方程如下：
dp[i][j]=max(dp[i-1][j-k*w[i]]+k*v[i])（在0<=k*value[i]<=j的情况下）
三、代码
代码如下：
#include <bits/stdc++.h>
using namespace std;
int dp[1000];
int w[100000],v[100000];
int main(){int m,n;cin>>m>>n;for(int i=1;i<=n;i++){cin>>w[i]>>v[i];}for(int i=1;i<=n;i++){for(int j=w[i];j<=m;j++){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<"max="<<dp[m];return 0;
}
例题
题目描述：
零崎有很多朋友，其中有一个叫做lfj的接盘侠。lfj是一个手残，他和零崎一起玩网游的时候不好好打本，天天看拍卖行，没过多久，就成为了一个
出色的商人。时间一长，虽然挣了不少钱，却没时间练级了。作为lfj的友人，零崎实在看不下去，于是他决定帮lfj一把。当然了，零崎肯定不会自己动手，活
还得你们来干。lfj可以提供给你们拍卖行所有能买到物品的价格和利润，由于游戏产出不限，所以可以假定只要有钱
，即使是同一种东西，多少个也都能买到手。lfj还会告诉你他初始的成本。虽然零崎想让你们给出
一次交易中利润最大的购买方案，但是lfj觉得只要知道最大利润就可以了。
输入：
每组数据第一行为两个整数P和N，表示本金和拍卖行物品种类数。接下来N行，每行两个数据pi,ci代表第i类物品的利润和购买价格。1<=P<=20000,1<=N<=300,1<=c,p<=200
输出
对于每组数据，输出一行，为能获得的最大利润
这道题是我从网上找的，可以用来练练手。没有样例，可以自己出几个样例测试一下自己的代码的正确性。
这篇关于c++ dp基础完全背包细讲的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
