题解 P2871 【[USACO07DEC]手链Charm Bracelet】

· · 题解

dalao请无视本篇垃圾题解

好久不做DP题了，拿一道经典的01背包来找找手感【01背包直接背代码的我~笑】

显然01背包的状态转移方程是:

for(int i=1;i<=n;i++)
 for(int v=V;v>=c[i];v--)
  f[v]=max(f[v],f[v-c[i]]+w[i]);

那么问题来了

为什么第二层循环是从V开始的？

其实原来我也不太明白，只是半知半解，今天才突然明白，果然我是最弱的QAQ

答：

从动态规划的基本思想来看，就是将体积为V的背包拆分为体积为Vi的背包，通过求每一种体积的01背包的最优解来构成目标体积的01背包的最优解的最优子结构

用通俗的语言来说就是：

设：当前背包内剩余的容量为v。

那么 f[v-c[i]]+w[i]即为装入体积为c[i]的物品，剩余容量-c[i]，获得的价值是w[i]

不妨我们枚举每一种Vi【信竞对数学的笑容：)】，从而获得第i种物品在容量为Vi的01背包中的最优状态（选或不选）由此我们便获得了最优子结构

为什么第一层循环是i？

反证法：

假设第一层循环是v

若当前有wi+wi>wj，那么我们就会选择两个i号物品，所以，枚举物品i需要在第一层循环进行

下面就是你们最爱的AC代码了OvO

#include<bits/stdc++.h>
#define maxn 23333 
using namespace std;
int n,V;
int c[maxn],w[maxn],f[maxn];
int main()
{
    cin>>n>>V;
    for(int i=1;i<=n;i++)cin>>c[i]>>w[i];
    for(int i=1;i<=n;i++)
     for(int v=V;v>=c[i];v--)
     {
        f[v]=max(f[v],f[v-c[i]]+w[i]);
     }
    cout<<f[V];
    return 0;
}