每日OJ题_牛客_[NOIP2001]装箱问题_01背包_C++_Java

目录

牛客_[NOIP2001]装箱问题_01背包

题目解析

C++代码

Java代码

---

牛客_[NOIP2001]装箱问题_01背包

[NOIP2001]装箱问题 (nowcoder.com)

描述：
        有一个箱子容量为V（正整数，0 ≤ V ≤ 20000），同时有n个物品（0＜n ≤ 30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

---

题目解析

01 背包简单应用。01背包类型题解：Offer必备算法25_01背包_四道力扣题详解（由易到难）_力扣 01背包-CSDN博客

C++代码

#include <iostream>
#include <vector>
#include <climits>
using namespace std;int main()
{int V = 0, n = 0;cin >> V >> n;vector<int> arr(n);    // 下面找原数组不-1的话就多开一个位置占位，输入[1,n]for(int i = 0; i < n; ++i){cin >> arr[i];}vector<vector<int>> dp(n + 1, vector<int>(V + 1));for(int i = 1; i <= n; ++i){for(int j = 0; j <= V; ++j){dp[i][j] = dp[i - 1][j];if(j >= arr[i - 1])dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i - 1]] + arr[i - 1]);}}cout << V - dp[n][V] << endl;return 0;
}

Java代码

import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in);int v = in.nextInt();int n = in.nextInt();int[] arr = new int[n + 1];for(int i = 1; i <= n; i++){arr[i] = in.nextInt();}int[][] dp = new int[n + 1][v + 1];for(int i = 1; i <= n; i++){for(int j = 0; j <= v; j++){dp[i][j] = dp[i - 1][j];if(j >= arr[i]){dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - arr[i]] + arr[i]);}}}System.out.println(v - dp[n][v]);}
}