题目描述

完全背包（动态规划）

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

10

二维三重循环

代码

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int  dp[1005][1005];
int main()
{
    int n, vi, v[1005], w[1005];
    scanf("%d%d", &n, &vi);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=vi;j++)
            for (int k = 0; k * v[i] <= j; k++)
            //k代表物品个数，并且总体积不超过j
            //k=0就相当于不含第i个物品
            {
                if (dp[i][j] <= dp[i - 1][j - k * v[i]] + k * w[i])
                    dp[i][j] = dp[i - 1][j - k * v[i]] + k * w[i];
            }
    printf("%d", dp[n][vi]);
    return 0;
}

二维二重循环

代码

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int  dp[1005][1005];
int main()
{
    int n, vi, v[1005], w[1005];
    scanf("%d%d", &n, &vi);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    for(int i=1;i<=n;i++)
        for (int j = 0; j <= vi; j++)//状态转移方程：f[i,j]=MAX{f[i-1,j],f[i][j-v[i]]+w[i]}
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) 
            {
                if (dp[i - 1][j] <= dp[i][j - v[i]] + w[i])
                    dp[i][j] = dp[i][j - v[i]] + w[i];
            }
        }
    printf("%d", dp[n][vi]);
    return 0;
}

一维写法

代码

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int  dp[1005];
int main()
{
    int n, vi, v[1005], w[1005];
    scanf("%d%d", &n, &vi);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    for(int i=1;i<=n;i++)
        for (int j = v[i]; j <= vi; j++)//j从小到大
        {
            if (dp[j] <= dp[j - v[i]] + w[i])
                dp[j] = dp[j - v[i]] + w[i];
        }
    printf("%d", dp[vi]);
    return 0;
}