本文主要是介绍acm动态规划中新数据对原始数据的干扰和排除，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
以下面的这道题为例。。
有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
一个整数v，表示箱子容量
一个整数n，表示有n个物品
接下来n个整数，分别表示这n 个物品的各自体积
一个整数，表示箱子剩余空间。
24
6
8
3
12
7
9
7
0
#include <iostream>
#include <cstring>
using namespace std;
int max(int x, int y)
{
return x>y?x:y;
}
int main()
{
int v,n;
freopen("1.txt","r",stdin);
scanf("%d%d",&v,&n);
int a[32];
int dp[20002];
memset(dp, 0, sizeof(dp));
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
for(int j=v; j>=a[i]; j--)
{
dp[j] = max(dp[j], dp[j-a[i]]+a[i]);
}
}
cout << v-dp[v];
while(1);
}
如果将上面的这个循环反着写。。。那么就不会AC了（除非只有一组凑得很好的数据）。。。
原因在与如果反着写，，，那么假设dp[4]被更新用了第一个物体。。。当dp[5]被更新成dp[4]+1的时候。。。会有什么问题呢。。。？可以看出在dp[5]中物体1用了2次。。。
PS:其实我觉得这道题嘛。。。就是用一个一个物体更新dp[v]...只不过在更新的时候要用到dp[1....v]所以也要将前面的也跟新。。。
这篇关于acm动态规划中新数据对原始数据的干扰和排除的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
