洛谷 P1049 01背包

https://www.luogu.org/problemnew/show/P1049

題目描述

有一個箱子容量為V（正整數，0≤V≤200000），同時有n個物品（0<n≤300)，每個物品有一個體積（正整數）。

要求n個物品中，任取若幹個裝入箱内，使箱子的剩餘空間為最小。

輸入輸出格式

輸入格式：

1個整數，表示箱子容量

1個整數，表示有n個物品

接下來n行，分别表示這n個物品的各自體積

輸出格式：

1個整數，表示箱子剩餘空間。

輸入輸出樣例

輸入樣例#1： 複制

24
6
8
3
12
7
9
7
      

輸出樣例#1： 複制

說明

NOIp2001普及組 第4題

思路：喜聞樂見的01背包的變形，認為物品價值與物品體積相等，那麼最大價值的情況即剩下的體積最少。

#include<iostream>
using namespace std;

int f[20005];
int w[35];

int main()
{
    int t,n;
    cin>>t>>n;
    for(int i=0;i<n;i++)    //0 1背包 重量與價值相等
        cin>>w[i];
    for(int i=0;i<n;i++)
        for(int j=t;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+w[i]);
    cout<<t-f[t]<<endl;
    return 0;
}