题目描述

这里确切的说，应该是加上了一些贪心思想
遍历物体时，会去找价值w 最大的
因为是 物品不限个数，所以每次遍历全部物体即可
n表示 物品数量
arr[n][2] 表示体积和价值
其中 arr[i][0] 表示物品 i 的体积
arr[i][1] 表示物品 i 的价值

dp[v] 表示每种容积下的最大价值
状态转移方程为 dp[i] = max(dp[i - arr[j][1]]+arr[j][0],dp[i])

i - arr[j][1] 表示放下 j物品后
+arr[j][0] 表示 加上j 物品的价值
dp[i] 表示不选 j物品

算法1

(dp) $O(n^2)$

从体积开始遍历

时间复杂度 o(nv)

java 代码

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int v = in.nextInt();
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = in.nextInt();//体积
            arr[i][1] = in.nextInt();//价值
        }


        int[] dp = new int[v+1];//用容积来递推
        for (int i = 1; i <=v ; i++) {
        //贪心去找价值最大的
            for (int j = 0; j < n; j++) { //遍历每种物品，逐个尝试，看看放下去的效果如何
               if(arr[j][0]<=i){  //看当前 容积 放不放得下改物品
                   dp[i] = Math.max(dp[i - arr[j][0]] + arr[j][1],dp[i]);
               }
            }
        }

        System.out.println(dp[v]);//注意是体积 v
    }
}

算法2

(dp) $O(n^2)$

从物品开始遍历

java 代码

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int v = in.nextInt();
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = in.nextInt();
            arr[i][1] = in.nextInt();
        }


        int[] dp = new int[v+1];
        for (int i = 0; i < n; i++) {//遍历物品
            for (int j = arr[i][0]; j <= v; j++) {  //遍历各个容积下，这个物品放下去后的价值,值不值得放
                dp[j] = Math.max(dp[j-arr[i][0]] + arr[i][1],dp[j]);
            }
        }

        System.out.println(dp[v]);
    }
}