洛谷 P1049 装箱问题

\[传送门在这呢！！\]

题目描述

有一个箱子容量为\(V\)（正整数，\(0 \le V \le 20000\)），同时有\(n\)个物品（\(0<n \le 30\)，每个物品有一个体积（正整数）。

要求\(n\)个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入输出格式

输入格式：

\(1\)个整数，表示箱子容量

\(1\)个整数，表示有\(n\)个物品

接下来\(n\)行，分别表示这\(n\)个物品的各自体积

输出格式：

\(1\)个整数，表示箱子剩余空间。

输入输出样例

输入样例#1：

24
6
8
3
12
7
9
7

输出样例#1：

0

说明

NOIp2001普及组 第4题

思路

一维背包解决......懒得写题解

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N=10005;

int dp[101011],n,w[N],m;

int main() {
    scanf("%d%d",&m,&n);
    for (int i=1; i<=n; i++) scanf("%d",&w[i]);
    for (int i=1; i<=n; i++) {
        for (int j=m; j>=w[i]; j--) {
            dp[j]=max(dp[j-w[i]]+w[i],dp[j]);
        }
    }
    int ans=m-dp[m];
    printf("%d\n",ans);
    return 0;
}