---
title: "装箱问题"
created: 2025-11-28
tags:
  - 算法
---

# 装箱问题

## 题目 [装箱问题](https://www.acwing.com/problem/content/1026/)

![[image-b1f59f01.png]]

## 思路分析

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

// 背包容积 V

// n个物品 体积v[i] 价值同体积

// 每个物品有选与不选两种选择 01背包

const int N=20010;

int v[N];

int f[N];

int dp[N][N];

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int m;cin>>m;

	int n;cin>>n;

	for(int i=1;i<=n;i++){

		cin>>v[i];

	}

//	for(int i=1;i<=n;i++){

//		for(int j=1;j<=m;j++){

//			dp[i][j]=dp[i-1][j];

//			if(j>=v[i])	dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+v[i]);

//		}

//	}

//

//	cout<<m-dp[n][m];

	for(int i=1;i<=n;i++){

		for(int j=m;j>=v[i];j--){

			f[j]=max(f[j],f[j-v[i]]+v[i]);

		}

	}

	cout<<m-f[m];

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[糖果|糖果]] 🏠 [[00-刷题理模型]] ➡️ [[采药|采药]]