跳至正文

NOIP_2001.PJ4:装箱问题 解题报告

  • OI路程

什么都不说了,简单的DP,直接上代码。
唯一注意的一点,我不是用的剩余做DP值,而是和普通的DP一样,最后再用总质量剪掉这个DP值。

C语言:

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))

int f[20001];

int main(void)
{
 int i, j, t;
 int v, m;
 scanf(%d%d, &v, &m);
 for(i = 0; i < m; i++){
 scanf(%d, &t);
 for(j = v; j >= t; j--){
 f[j] = max(f[j], f[j - t] + t);
 }
 }
 printf(%d\\n, v - f[v]);
 return 0;
}

发表评论

您的电子邮箱地址不会被公开。