动态规划—01背包复习

解题思路:

注意事项:

参考代码:

#include<stdio.h>

#define max(x,y) x>y?x:y
int v[60] = { 0 };//物品价值
int w[60] = { 0 };//物品重要度
int q[60] = { 0 };//物品是主件还是附件
int dp[60][32000] = { 0 };//在i件物品、N元下，最大总和

int main()
{
    int N = 0, k = 0;
    scanf("%d%d", &N, &k);
    for (int i = 1; i <= k; i++)
    {
        scanf("%d%d%d", &v[i], &w[i], &q[i]);
    }
    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (j < v[i])//价值大于预算
            {
                dp[i][j] = dp[i - 1][j];//当前物品买不了，则i种物品最大总和等于i-1种物品的最大总和
            }
            else
            {
                if (q[i] == 0)//当前物品为主件
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + v[i] * w[i]);//取最大值
                }
                else//当前物品为附件,则必须购买对应主件
                {
                    if (j < v[i] + v[q[i]])//主件加附件的价值超过预算
                    {
                        dp[i][j] = dp[i - 1][j]; //当前附件买不了,则i种物品最大总和等于i-1种物品的最大总和
                    }
                    else
                    {
                        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i] - v[q[i]]] + v[i] * w[i] + v[q[i]] * w[q[i]]);
                    }
                }
            }
        }

    }
    printf("%d", dp[k][N]);//k种物品，N元预算下，最大总和
    return 0;
}