Question

01背包问题

百度百科上的一个算法：
#include "stdafx.h"
#include <iostream>
using namespace std;
#define MAXSIZE 1000
int f[MAXSIZE + 1],c[MAXSIZE + 1],w[MAXSIZE + 1];
int _tmain(int argc,_TCHAR* argv[])
{
int N,V;
cin >> N >> V;
int i = 1;
for (; i <= N; ++i)
{
cin >> c[i] >> w[i];
}
for (i = 1; i <= N; ++i)
{
for (int v = V; v >= c[i]; --v) //c[i]可优化为bound,bound = max {V - sum c[i,...n],c[i]}
{
f[v] = (f[v] > f[v - c[i]] + w[i])?f[v] : f[v - c[i]] + w[i];
}
}
//当i=N时，可以跳出循环单独计算F[V]
cout << f[V] << '\n';
system("pause");
return 0;
}

为什么for (int v = V; v >= c[i]; --v) 这里V为什么逆序
百度百科上的原话看不懂啊 （我怎么这么笨啊。。。）：
f[i][v]是由f[i-1][v]和f [i-1][v-c[i]]两个子问题递推而来，能否保证在推f[v]时（也即在第i次主循环中推f[v]时）能够得到f[v]和f[v -c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值

Answer 1

就是所谓01背包，一个物品只能被用一次，因此当状态简化为一维(即f[])时，f[v]是从f[v - c[i]]
转移而来，所以，为了保证只用一次就需要倒序枚举了。
二维状态的时候就没关系。

追问

为什么保证只用1次就是倒叙枚举啊 虽然顺序枚举明显会减成负数 好难想啊
我好像懂了一些了 但是这算法 要实打实想出来不好想啊 怎么想到这样写的啊

追答

原本状态是2维，f[i][v]是从f[i - 1][v - c[i]]转移而来。但是现在你要化简为1维。所以状态f[v]是从f[v - c[i]]转移而来，这时如果顺序枚举，f[v - c[i]]并不是二维时的f[i - 1][v - c[i]]，可能己经被更新，这样就出现了被装多次的情况，是不对的。（和减成复数没关系- -）

其实不难想的，最直观的是自己画一画状态图。

01背包化成一维并不难，但其他题若很难想到化成1维的办法，二维也是其实也是很不错的，可以用滚动数组来优化。（当然这个题还是要搞明白的）

追问

自己输入了一些测试数据 终于又懂了一些 原来是数组以前的值被赋值了 倒叙是为了在一次内层循环中·慢慢递减出去 离开内层循环 不然可能取重复值？ 也不是特别懂好像

追答

呃，差不多就是这意思吧。尽可能脱离代码搞清楚本质。
二维状态转移你懂吧？

追问

我突然发现我的问题不止是这里 就是为什么v那块要循环啊 。。 我觉得只算一次就够了啊 v为什么要一次次的递减 算出每一个f[v]值 比如 v=99 f[99]有什么意义 又没有输入重量为1的物品
我有点笨 告诉我下吧 哈哈

Answer 2