【小马刷题笔记】完全背包问题-动态规划-Java（ACM版本）

题目概述：

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式：

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式：

输出一个整数，表示最大价值。

数据范围：

0 0

输入样例：

4 5
1 2
2 4
3 4
4 5

输出样例：

10

解题思路：

       这道题的思路和01背包非常相似，唯一的不同是：01背包中的每个物品只能用一次，而完全背包中的每个物品都可以用无限次，都是求在一定体积中可装入的物品的最大值。运用动态规划的思想，定于一个dp数组，设物品数量为count，背包总体积为sum，数组volumes表示每个物品的体积，数组values表示每个物品的价值，dp[count+1][sum+1]；dp[i][j]表示在体积为 j 的背包里有 i 件物品可选的情况下的最大价值（每件物品可以使用无限次）。

 嵌套 for 循环，每次增加一个可选物品，有两种情况：

        第一种：此件可选物品的体积大于目前背包的体积：

               物品体积大于背包体积时，背包无法装下此物品（即不装此物品），则dp[i][j]=dp[i-1][j]

        第二种：此件可选物品的体积小于等于目前背包的体积：

              物品提交小于等于背包体积时，可以选择装此物品和不装此物品，

         由于每件物品都可以使用无限次，则在装此物品时的取值为dp[i][j-volumes[i]]+values[i];

              dp[i][j]=Math.max(dp[i-1][j],dp[i][j-volumes[i]]+values[i]);

             取两者的最大值

       最终返回dp[count][sum]为结果。

完整代码：

import java.util.*;
public class CompletePack {
    public int solve(int count,int sum,int[] volumes,int[] values){
        if(count==0 || sum==0) return 0;
        int[][] dp=new int[count+1][sum+1];
        for(int i=1;i