首先完全背包问题和背包问题除了一点不同，其他完全相同，不同就是每个物品可以无限次可用。

题目：题目链接

image.png

  2. import java.util.Scanner;
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner sc=new Scanner(System.in);
  7.         int N=sc.nextInt();
  8.         int V=sc.nextInt();
  9.         int[] f=new int[V+1];
  10.         for(int i=1;i<=N;i++) {
  11.             int v=sc.nextInt();
  12.             int w=sc.nextInt();
  13.             //这里这个从v开始  原因和01背包基础版是一样的，就是之前的不用更改所以不用算
  14.             //其实你有没有发现，他们不算的部分都是一样的，就是都是前面的一部分不用算。。。
  15.             for(int j=v;j<=V;j++) {
  16.                 f[j]=Math.max(f[j],f[j-v]+w);
  17.             }
  18.         }
  19.         System.out.println(f[V]);
  20.     }
  21. }

上面的代码是最优化的了（背包九讲pdf上我觉得优化就不看了，有点蒙，直接吧这个当最优吧）

联系题1：题目链接

image.png
经典的完全背包问题，虽然问法求的都变了，但是万变不离其宗

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         //首先是无限次使用，然后是给定一些凑一个数   完全背包问题
  4.         //而且是恰好可以凑到，而不是满足求价值了
  5.         //初始化，除了dp[0]其他都是-无穷大
  6.         int[] dp=new int[amount+1];
  7.         dp[0]=0;
  8.         for(int i=1;i<amount+1;i++){
  9.             dp[i]=0x3f3f3f3f;//-∞
  10.         }
  11.         for(int i=0;i<coins.length;i++){
  12.             for(int v=coins[i];v<=amount;v++){
  13.                 dp[v]=Math.min(dp[v],dp[v-coins[i]]+1);
  14.             }
  15.         }
  16.         return dp[amount]!=0x3f3f3f3f?dp[amount]:-1;
  17.     }
  18. }

看看这 行云流水 1分钟不到搞定，但是看看我以前写的代码，乱八七早

练习题2：题目链接

image.png

  1. class Solution {
  2.     public int change(int amount, int[] coins) {
  3.         int[] dp=new int[amount+1];
  4.         dp[0]=1;
  5.         for(int i=0;i<coins.length;i++){
  6.             for(int j=coins[i];j<=amount;j++){
  7.                 dp[j]=dp[j]+dp[j-coins[i]];
  8.             }
  9.         }
  10.         return dp[amount];
  11.     }
  12. }