java 牛客网之[动态规划 中等]NC12 【模板】完全背包

java 牛客网之[动态规划 中等]NC12 【模板】完全背包

题目的链接在这里：https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc

目录

• 题目大意
• 一、示意图
• 二、解题思路
• • 完全背包问题

---

题目大意 你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为v_iv
i
​
,价值为w_iw
i
​
。

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？

---

一、示意图

二、解题思路

完全背包问题

完全背包问题

代码如下：

import java.util.*;

public class  Main{
  public static void main(String[] args) {
      Scanner sc=new Scanner(System.in);
      int n=sc.nextInt();
      int V=sc.nextInt();
      int[][] dp=new int[n+1][V+1];
      int[][] dp1=new int[n+1][V+1];
      //一样的 对dp进行最小值的初始化
      for(int i=1;i<=V;i++){
          //这些都是不合法的 除了0 0
          dp1[0][i]=Integer.MIN_VALUE;
      }
      int k=n;
      int l=1;
      int[] value=new int[n+1];
      int[] w=new int[n+1];
      while (k-->0){
          w[l]=sc.nextInt();
          value[l]=sc.nextInt();
          l++;
      }
      //这个就是完全背包问题
      for(int i=1;i<=n;i++){
          for(int j=0;j<=V;j++){
              
              //那就进行一个短暂统计
              int max=dp[i-1][j];
              int max1=dp1[i-1][j];
              
              for(int p=0;p<=(j/w[i]);p++){
                  //那就是让p[i-1][j] 也就是不选和 选一个 两个。。。p个进行判断
                  max=Math.max(max,dp[i-1][j-(p*w[i])]+p*value[i]);
                  max1=Math.max(max1,dp1[i-1][j-(p*w[i])]+p*value[i]);

              }
              dp[i][j]=max;
              dp1[i][j]=max1;
          }
      }

      //然后再输出即可 他这里输入的全是0
      System.out.println(dp[n][V]);
      dp1[n][V]=dp1[n][V]>0?dp1[n][V]:0;
      System.out.println(dp1[n][V]);
  }
  }