DP42?【模板】完全背包
题目描述：
描述
你有一个背包，最多能容纳的体积是V。
现在有n种物品，每种物品有任意多个，第i种物品的体积为��vi??,价值为��wi?。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数��vi?和��wi?，表示第i种物品的体积和价值。
1≤�,�≤10001≤n,V≤1000
输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
解题思路：
算法思路：
背包问题的状态表??常经典，如果?家不知道怎么来的，就把它当成?个模板记住吧~
我们先解决第?问：
1.
状态表?：
dp[i][j]
表?：从前
i
个物品中挑选，总体积不超过
j
，所有的选法中，能挑选出来的最
?价值。（这?是和 01背包?样哒）
2.
状态转移?程：
线性
dp
状态转移?程分析?式，?般都是根据最后?步的状况，来分情况讨论。但是最后?个
物品能选很多个，因此我们的需要分很多情况：
i.
选
0
个第
i
个物品：此时相当于就是去前
i - 1
个物品中挑选，总体积不超过
j
。
此时最?价值为
dp[i - 1][j]
；
ii.
选
1
个第
i
个物品：此时相当于就是去前
i - 1
个物品中挑选，总体积不超过
j -
v[i]
。因为挑选了?个
i
物品，此时最?价值为
dp[i - 1][j - v[i]] +
w[i]
；
iii.
选
2
个第
i
个物品：此时相当于就是去前
i - 1
个物品中挑选，总体积不超过
j
- 2 * v[i]
。因为挑选了两个
i
物品，此时最?价值为
dp[i - 1][j - 2 *
v[i]] + 2 * w[i]
；
iv.
......
综上，我们的状态转移?程为：
dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i], dp[i-1][j-
2*v[i]]+2*w[i]...)
当我们发现，计算?个状态的时候，需要?个循环才能搞定的时候，我们要想到去优化。优化的?
向就是??个或者两个状态来表?这?堆的状态，通常就是?数学的?式做?下等价替换。我们发
现第?维是有规律的变化的，因此我们去看看
dp[i][j - v[i]]
这个状态：
dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2*v[i]]+w[i],dp[i-1]
[j-3*v[i]]+2*w[i]...)
我们发现，把
dp[i][j - v[i]]
加上
w[i]
正好和
dp[i][j]
中除了第?项以外的全部
?致，因此我们可以修改我们的状态转移?程为：
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
。
3.
初始化：
我们多加??，?便我们的初始化，此时仅需将第??初始化为
0
即可。因为什么也不选，也能
满?体积不?于
j
的情况，此时的价值为
0
。
4.
填表顺序：
根据状态转移?程，我们仅需从上往下填表即可。
5.
返回值：
根据状态表?，返回
dp[n][V]
。
接下来解决第?问：
第?问仅需微调?下
dp
过程的五步即可。
因为有可能凑不?
j
体积的物品，因此我们把不合法的状态设置为
-1
。
1.
状态表?：
dp[i][j]
表?：从前
i
个物品中挑选，总体积正好等于
j
，所有的选法中，能挑选出来的
最?价值。
2.
状态转移?程：
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
。
但是在使?
dp[i][j - v[i]]
的时候，不仅要判断
j >= v[i]
，?要判断
dp[i][j -
v[i]]
表?的情况是否存在，也就是
dp[i][j - v[i]] != -1
。
3.
初始化：
我们多加??，?便我们的初始化：
i.
第?个格?为
0
，因为正好能凑?体积为
0
的背包；
ii.
但是第??后?的格?都是
-1
，因为没有物品，?法满?体积?于
0
的情况。
4.
填表顺序：
根据状态转移?程，我们仅需从上往下填表即可。
5.
返回值：
由于最后可能凑不成体积为
V
的情况，因此返回之前需要特判?下。
?解题代码：
#include <iostream>
#include<string.h>
#include<vector>
using namespace std;
int n, V;
const int N = 1010;
int v[N], w[N];
int dp[N];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
dp[j] = dp[j];
if (j >= v[i]) dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V] << endl;
memset(dp,0,sizeof(dp));
for(int j=1;j<=V;j++)dp[j]=-1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=V;j++)
{
dp[j]=dp[j];
if(j>=v[i]&&dp[j-v[i]]!=-1)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
return 0;
}
322. 零钱兑换
322.?零钱兑换
题目描述：
给你一个整数数组?coins?，表示不同面额的硬币；以及一个整数?amount?，表示总金额。
计算并返回可以凑成总金额所需的?最少的硬币个数?。如果没有任何一种硬币组合能组成总金额，返回?-1?。
你可以认为每种硬币的数量是无限的。
解题思路：
算法思路：
先将问题「转化」成我们熟悉的题型。
i.
在?些物品中「挑选」?些出来，然后在满?某个「限定条件」下，解决?些问题，?概率
是「背包」模型；
ii.
由于每?个物品都是?限多个的，因此是?个「完全背包」问题。
接下来的分析就是基于「完全背包」的?式来的。
1.
状态表?：
dp[i][j]
表?：从前
i
个硬币中挑选，总和正好等于
j
，所有的选法中，最少的硬币个
数。
2.
状态转移?程：
线性
dp
状态转移?程分析?式，?般都是根据「最后?步」的状况，来分情况讨论。但是最后
?个物品能选很多个，因此我们的需要分很多情况：
i.
选
0
个第
i
个硬币：此时相当于就是去前
i - 1
个硬币中挑选，总和正好等于
j
。
此时最少的硬币个数为
dp[i - 1][j]
；
ii.
选
1
个第
i
个硬币：此时相当于就是去前
i - 1
个硬币中挑选，总和正好等于
j -
v[i]
。因为挑选了?个
i
硬币，此时最少的硬币个数为
dp[i - 1][j -
coins[i]] + 1
；
ii.
选
2
个第
i
个硬币：此时相当于就是去前
i - 1
个硬币中挑选，总和正好等于
j
- 2 * coins
。因为挑选了两个
i
硬币，此时最少的硬币个数为
dp[i - 1][j -
2 * coins[i]] + 2
；
iv.
......
结合我们在完全背包??的优化思路，我们最终得到的状态转移?程为：
dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1)
。
这?教给?家?个技巧，就是相当于把第?种情况
dp[i - 1][j - coins[i]] + 1
?
?的
i - 1
变成
i
即可。
3.
初始化：
初始化第??即可。
这?因为取
min
，所以我们可以把?效的地?设置成?穷?
(0x3f3f3f3f)
因为这?要求正好凑成总和为
j
，因此，需要把第??除了第?个位置的元素，都设置成?穷
?。
4.
填表顺序：
根据「状态转移?程」，我们仅需「从上往下」填表即可。
5.
返回值：
根据「状态表?」，返回
dp[n][V]
。但是要特判?下，因为有可能凑不到。
解题代码：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
const int INT=0x3f3f3f3f;
int n=coins.size();
vector<vector<int>>dp(n+1,vector<int>(amount+1));
for(int j=1;j<=amount;j++) dp[0][j]=INT;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=amount;j++)
{
dp[i][j]=dp[i-1][j];
if(j>=coins[i-1])
dp[i][j]=min(dp[i][j],dp[i][j-coins[i-1]]+1);
}
}
return dp[n][amount]>=INT?-1:dp[n][amount];
}
};