[AcWing]-完全背包问题-动态规划

目录

一、题目描述

二、整体思路

三、代码

一、题目描述

题目地址

二、整体思路

        和01背包问题基本一样，唯一不同的是每件物品可以取无限次。

        dp数组的设置是一样的，在选择是否放入第i件物品时，物品体积大于背包当前容量的情况和01背包问题一样。所不同的是这件物品要取多少次。那么可以遍历最大放入次数，找出最大的总价值的情况。注意遍历过程中要更新dp[i][j]

三、代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int m=scanner.nextInt();
        int n=scanner.nextInt();
        int[] volume=new int[m+1];
        int[] value=new int[m+1];
        for(int i=1;i<=m;i++){
            int vi=scanner.nextInt();
            int wi=scanner.nextInt();
            volume[i]=vi;
            value[i]=wi;
        }
        System.out.print(dynamatic(m,n,volume,value));
    }
    public static int dynamatic(int m,int n,int[] volume,int[] value){
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<=n;i++){
            dp[0][i]=0;
        }
        for(int j=0;j<=m;j++){
            dp[j][0]=0;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(volume[i]>j){
                    dp[i][j]=dp[i-1][j];
                }else{
                    int k=j/volume[i];//该物品能放入的最多次数
                    for(int l=0;l<=k;l++){//遍历过程中要更新dp[i][j]
                        dp[i][j]=Math.max(dp[i][j],dp[i-1][j-l*volume[i]]+l*value[i]);
                    }
                    
                }
                
            }
        }
        return dp[m][n];
    } 
}