2.1 题目
有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品
的费用是 Ci，价值是 Wi。求解：将哪些物品装入背包，可使这些物品的耗费的费用总
和不超过背包容量，且价值总和最大。
2.2 基本思路
这个问题非常类似于 01 背包问题，所不同的是每种物品有无限件。也就是从每种
物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2
件……直至取 ⌊V /Ci⌋ 件等许多种。
如果仍然按照解 01 背包时的思路，令 F[i, v] 表示前 i 种物品恰放入一个容量为 v
的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
F[i,v] = max{F[i-1,v-kCi]+KWi}, 0<=kCi <=V
或者
F[i,v] = max(F[i-1,v],F[i,v-Ci]+Wi) 与01背包不同之处仅仅在于第二项的i是否可以重复取，遍历时是顺序。
例题：https://leetcode-cn.com/problems/coin-change/
322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1</pre>
示例 2：
输入：coins = [2], amount = 3
输出：-1</pre>
示例 3：
输入：coins = [1], amount = 0
输出：0
class Solution {
public int coinChange(int[] coins, int amount) {
// 完全背包问题
// dp[i][j] 背包容量为j，前i个元素的最大价值;
// 定义改成 和为j，前i个元素，的最少个数;
// result : dp[M][amount]
// 转移方程：dp[i][j] = Math.min(dp[i-1][j],dp[i][j-coins[i]]+1);
int m = coins.length;
int[][] dp = new int[m+1][amount+1];
// init
for(int j=1;j<amount+1;j++){
dp[0][j] = 0x3f3f3f3f;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=amount;j++){
if(j-coins[i-1]>=0){
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[m][amount]==0x3f3f3f3f? -1: dp[m][amount];
}
}
转成一维数组：
class Solution {
public int coinChange(int[] coins, int amount) {
// 完全背包问题
// dp[i][j] 背包容量为j，前i个元素的最大价值;
// 定义改成 和为j，前i个元素，的最少个数;
// result : dp[M][amount]
// 转移方程：dp[i][j] = Math.min(dp[i-1][j],dp[i][j-coins[i]]+1);
int m = coins.length;
int[] dp = new int[amount+1];
// init
for(int j=1;j<amount+1;j++){
dp[j] = 0x3f3f3f3f;
}
for(int i=1;i<=m;i++){
for(int j=coins[i-1];j<=amount;j++){
dp[j] = Math.min(dp[j],dp[j-coins[i-1]]+1);
}
}
return dp[amount]==0x3f3f3f3f? -1: dp[amount];
}
}
