P1049 [NOIP2001 普及组] 装箱问题（dp）C/C++_装箱问题 c++

P1049 [NOIP2001 普及组] 装箱问题

因为每个物体，都有装与不装两种选择，所以我们得到状态转移方程：
f[j]=max(f[j],f[j-w[i]]+w[i]);

f[j] 为：当总容量为 j 时，不放第 i 件物品，所能装的最大体积。
f[j-w[i]]+w[i] 为：当总容量为 j 时，放了第 i 件物品后，所能装的最大体积。（即 j减去第 i 件物品体积 的容量能装的最大体积+第 i 件物品的体积。w[i] 为第 i 件物品体积）

#include<iostream>
#include<cstdio>
using namespace std;
int f[20005],w[35];
int main()
{
    int v,n;
    cin>>v>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=v;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+w[i]);
    cout<<v-f[v];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15