[動态規劃] 洛谷P1049 裝箱問題 （01背包）

題目

LP1049

思路

本題唯一難度在于發現，問題的隐藏價值W[i] = V[i]。厘清消耗量與價值量，并且有時它們甚至還會相等。

剩下的就是裸01背包。

代碼

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define _for(i,a,b) for(int i = (a); i<(b); i++)
#define _rep(i,a,b) for(int i = (a); i<=(b); i++)
using namespace std;

const int maxx = +;
int n, C, d[maxx];

int main(){
    scanf("%d%d",&C,&n);
    int V;
    _rep(i,,n){
        scanf("%d",&V);
        for(int j = C; j>=; j--)
            if(j >= V)
                d[j] = max(d[j],d[j-V]+V);
    }
    printf("%d\n",C-d[C]);

    return ;
}