题解 | 【模板】完全背包

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int t=scanner.nextInt();
		while(t-->0) {
			int n=scanner.nextInt();
			int m=scanner.nextInt();
			int w[]=new int[n];//体积
			int v[]=new int[n];//价值
			for (int i = 0; i < v.length; i++) {
				w[i]=scanner.nextInt();
				v[i]=scanner.nextInt();
			}
			int dp[]=new int[m+1];
			for (int i = 0; i < n; i++) {
				for (int j = w[i]; j <= m; j++) {
					dp[j]=Math.max(dp[j], dp[j-w[i]]+v[i]);
				}
			}
			System.out.println(dp[m]);
		}

	}

}

与01背包很像，主要的区别时01背包遍历dp数组时是逆序，而完全背包是正序，正序使得第i件物品可以多次选择