每天经受2道代码的小白写的一个背包问题

解题思路:

注意事项:

参考代码:

/*装箱问题。有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，
每个物品有一个体积  (正整数)。要求从  n  个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 
* 输入：
        第一行，一个整数，表示箱子容量；  第二行，一个整数，表示有n个物品；  
        接下来n行，分别表示这n个物品的各自体积。 
* 输出：
        一个整数，表示箱子剩余空间。      */

#include<stdio.h>
#define Max(a,b) a>b?a:b;
int dp[32][19999] = { 0 };
int main()
{
    
    int v = 0;
    int wu[32] = { 0 };
    int i = 0;
    int f = 0;
    int j = 0;
    int n = 0;
    f = scanf("%d%d", &v, &n);
    for (i = 0; i < n; i++)
    {
        f = scanf("%d", &wu[i]);
    }
    //初始化
    for (i = 0; i < n; i++)
    {
        dp[i][0] = 0;
    }
    for (j = v; j >= wu[0]; j--)
    {
        dp[0][j] = dp[0][j - wu[0]] + wu[0];

    }
   //递推
    for (i = 1; i < n; i++)//对人遍历
    {
        for (j = 0; j <= v; j++)//对每个j遍历
        {
            if (j < wu[i])//物品i不选
            {
                dp[i][j] = dp[i - 1][j];
            }
            else
            {

                dp[i][j] = Max(dp[i - 1][j], (dp[i - 1][j - wu[i]] + wu[i]));//递推
            }
        }//打印dp

    }
    /*for (i = 0; i < n; i++)
    {
        for (j = 0; j <= v; j++)
        {
            printf("%d ", dp[i][j]);
        }
        printf("\n");
    }
    */
    printf("%d", v - dp[n-1][v]);


}