一个旅行者有一个最多能用M公斤的背包,现在有N件物品,

1个回答

  • 这个是状态转移方程

    f[v] 表示背包剩余容量V时候积累的价值总和

    你这个是优化版本的只用了一维数组 有个更基本的方法我解释给你听

    有n件物品 假设当前到第i件了

    { f[i - 1][v];

    f[i][v](到第i件时 此时容量为v ) = {

    { f[i - 1][v - w[i]] + p[i];(v>=w[i])

    (两者中较大的那个)

    “将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题.如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i].