三种基本背包问题

一、0/1背包问题

问题描述：有n件物品和容量为m的背包 给出i件物品的重量以及价值 求解让装入背包的物品重量不超过背包容量 且价值最大 。
特点:这是最简单的背包问题，特点是每个物品只有一件供你选择放还是不放。
① 二维解法
设f[i][j]表示前 i 件物品 总重量不超过 j 的最大价值 可得出状态转移方程
f[i][j]=max{f[i-1][j-a[i]]+b[i], f[i-1][j]}

代码： 
for(int i=1;i<=n;i++)
    for(int j=m;j>0;j--){
        if(a[i]<=j)
           f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]);
        else f[i][j]=f[i-1][j];
    }

在一些情况下 题目的数据会很大 因此f数组不开到一定程度是没有办法ac。

②一维解法
设f[j]表示重量不超过j公斤的最大价值 可得出状态转移方程
f[j]=max{f[j], f[j−a[i]]+b[i]}

 代码：
 for(int i=1;i<=n;i++){       
      for(int j=m;j>=a[i];j--)
          f[j]=max(f[j], f[j-a[i]]+b[i]);  
    }

二、完全背包问题

问题描述：有n件物品和容量为m的背包 给出i件物品的重量以及价值 求解让装入背包的物品重量不超过背包容量 且价值最大 。
特点：题干看似与01一样 但它的特点是每个物品可以无限选用。

设f[j]表示重量不超过j公斤的最大价值 可得出状态转移方程
f[j] = maxj{f[j], f[j−a[i]]+b[i]}

代码：
for(int i=1;i<=n;i++)
    for(int  j = a[i];j <= m;j++){
        f[j] = max(f[j], f[j-a[i]]+b[i]);
    }

三、多重背包问题

问题描述：有n件物品和容量为m的背包 给出i件物品的重量以及价值 还有数量 求解让装入背包的物品重量不超过背包容量 且价值最大 。
特点 ：它与完全背包有类似点 特点是每个物品都有了一定的数量。

状态转移方程为：
f[j] = max{f[j], f[j−k∗a[i]]+k∗b[i]}

    for(int i=1;i<=n;i++)
    for(int j=m;j>=a[i];j--)
    for(int k=0;k<=c[i];k++){
        if(j-k*a[i]<0)break;
        f[j] = max(f[j], f[j-k*a[i]]+k*b[i]);
    }

实战：

题目一：
链接：https://leetcode-cn.com/problems/coin-change-2/ 力扣（LeetCode）
题目：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1：
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

class Solution {
    public int change(int amount, int[] coins) {
        int []dp=new int[amount+1];
        dp[0]=1;
        for(int coin:coins){
            for(int i=coin;i<=amount;i++){
                dp[i]=dp[i]+dp[i-coin];
            }
        }
       return dp[amount];        
    }
}