题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 1…N。
数据范围
0<N,V≤1000
0<vi,wi≤1000

样例

输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
1 4

算法1

dp逆序，把当前物品i的状态看作是终点，而非起点，不用滚动数组，方便由该状态确定
确定当前物品是否被选中，dp[1][V]即为最大结果，也是dp状态的最终解，依此状态逆推
，如果此物品 dp[i][now] == dp[i + 1][now - ali[i].v] + ali[i].w，就说明，最终状
态的解中，可以包括这个物品，因为是字典顺序枚举，所以可以要就等于一定要，毕竟，
若不要此物品，从dp[i+1][V]推到dp[N+1][0]也是有可能成立的一种方案，只不过不是
最小字典序；

Tips：最后一个方案没过：

  输出：    1 2 4 8 10 168 211 271 315

  标准答案：1 2 4 8 10 168 211 271 434 

原因：数组的越界，转移方程 dp[i][now] == dp[i + 1][now - ali[i].v] + ali[i].w，
如果ali[i].v大于now则访问的是一个越界地址，该地址的值可能为任何值，刚刚测试了
一下，visual studio 是 0，并且越界不会报错；此时若 0 + ali[i].w == dp[i][now],
那么i不就是错的数据吗，这应该是我的最后一个数据与答案不一致的原因吧！！！

测试代码：

          int m = 1;
          int ll;
          int kk = dp[m - 20][0];

反汇编结果：

00C71B73  mov         eax,dword ptr [m]  
00C71B76  sub         eax,14h  
00C71B79  imul        ecx,eax,0FBCh  

编译器并不会按我的预想报错，而是把m偏移20地址的数据提取了出来，kk=0,
而未赋值的ll却等于-858993460；会不会是等于号赋值失败就返回0导致，而不是
data段的值导致的呢？反正编译器对越界不会报错，那我就越界改数据段的值，再
看看kk会是多少就知道了啊，于是就有了下面的代码：

    int m = 1;
    int ll;
    dp[m - 20][0] = 1;
    int kk = dp[m - 20][0];

结果显示ll还是-858993460，而kk是1，这证明了刚刚的猜想，不是等于号的返回值的
问题，这就是数组越界，而数据段的这个数据是正常情况下我们访问不到的，导致的答案
错误；

为什么越界不会报错？？？那我用编译器改电脑的注册表计算机不就爆炸了？？？（嘿嘿），

001F1B73  mov         eax,dword ptr [m] 
EDX = 008FF918

通过这里的反汇编我发现m数据段应该在008FF918，数据表应该在前面，所以就有了这个代码

dp[m - （0x008FF918/32）][0] = 1;

哎，编译器还是蛮安全的，报错了：

0x00C21B89 处(位于 Project1.exe 中)引发的异常: 
0xC0000005: 写入位置 0x17FC0F08 时发生访问冲突。

这应该是我见过最常见的越界提示了；

可是为什么我的dp[m - 20][0] = 1;不会报错呢，我的胡乱猜想应该是因为：
dp[m - 20][0]虽然对于二维数组越界，但显然对数据段没有越界，寻址范围没有超过数据段，
而编译器对越界的判定应该是超过了某个特定区段才是；例如本题的data段，对于汇编的知识
我也没了解多少，内行又有耐心看完我文章的同学发现我的分析有误的话，欢迎提出我的错误。

C++ 代码

#include<iostream>
#include<algorithm>

struct kk
{
    int v, w;
}ali[1007];
int N, V, flag = 0;
int dp[1007][1007] = { {} };

int main(void)
{
    scanf("%d %d", &N, &V);
    for (int i = 1; i <= N; i++)scanf("%d %d", &ali[i].v, &ali[i].w);

    for (int i = N; i >= 1; i--)
        for (int v = 0; v <= V; v++)
            if (v >= ali[i].v)dp[i][v] = std::max(dp[i + 1][v - ali[i].v] + ali[i].w, dp[i + 1][v]);
            else dp[i][v] = dp[i + 1][v];

    int now = V, flag = 0;
    for (int i = 1; i <= N; i++)
        if (dp[i][now] == dp[i + 1][now - ali[i].v] + ali[i].w && now >= ali[i].v)
        {
            if (flag)putchar(' ');
            else flag = 1;
            now -= ali[i].v;
            printf("%d", i);
            if (!now)break;
        }
    putchar('\n');
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla