大学计算机-背包问题 求解 ，答案

背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量
内，我们如何选择，才能使得物品的总价格最高。下图是背包问题的一个例子，应该选择哪
些盒子，才能使价格尽可能地大，并且保持总重量不超过 15 kg？所选物品的总价值是多少？

题主，上一个给你发的那个输入顺序换下就对了，不用重新发题

//一维数组解法
#include<stdio.h>
#define MAX_M 12880        //最大限重
#define MAX_N 3402        // 最大种类数
#define max(a,b) a>b?a:b
int dp[MAX_M + 1]={0};
int weights[MAX_N + 1];
int values[MAX_N + 1];
int main() {
    int n, m, i, j;
    scanf("%d%d", &n , &m);//n是种类，m是限制重量
    for (i = 1; i <= n; i++) {
        scanf("%d%d", &values[i],&weights[i] );
    }
    for (i = 1; i <= n; i++) {
        for (j = m; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    printf("%d\n", dp[m] );
}
/*
5 15
4 12
2 2
2 1
1 1
10 4
*/
 

哈喽，看看这个，有用请点采纳哦

/*背包问题:
背包所能容纳重量为10；共五件商品，商品重量用数组m存储m[5]={12,2,1,1,4 },
每件商品的价值用数组n存储,n[5]={ 4,2,2,1,10 };求背包所能装物品的最大价值。
*/
#include<stdio.h>
#include<conio.h>
int main() {
    int m[5] = {12,2,1,1,4 }, n[5] = { 4,2,2,1,10 };
    int flag[5] = { 0,0,0,0,0 };//符号标志位，表示地某个点是否装入背包，装入为1，未装入为0；
    int i, j, k;
    int c = 15, sum1 = 0, sum2 = 0;//sum1表示最终背包容纳的重量。sum2表示最终背包中容纳的最大价值的价值。
                                   //设一个二维数组，横坐标表示所装物品的标号，纵坐标表示背包所容纳的最大重量0~15；
    int mn[5][16];
    for (i = 4; i >= 0; i--) {//二维数组从下至上
        for (j = 0; j <= 15; j++) {
            if (i == 4) {
                if (m[i]>j)
                    mn[i][j] = 0;
                else
                    mn[i][j] = n[i];
            }
            else {
                if (m[i]>j) {
                    mn[i][j] = mn[i + 1][j];
                }
                else {
                    mn[i][j] = mn[i + 1][j]>mn[i + 1][j - m[i]] + n[i] ? mn[i + 1][j] : mn[i + 1][j - m[i]] + n[i];
                }
            }
        }
    }

    for (i = 0; i<5; i++) {
        if (mn[i][c] != mn[i + 1][c]) {//从二维数组上方开始，背包最大值c,mn[i][c]的值若与mn[i+1][c]的值不同，则m[i]未放入背包中（之前是自下往上放的）
            flag[i] = 1;
            c = c - m[i];//若放入背包，则背包可容纳总重量减少；
        }
        printf("%d ", flag[i]);      // 输出每一种的数量
    }

    for (i = 0; i<5; i++) {
        if (flag[i] == 1) {
            sum1 += m[i];
            sum2 += n[i];
        }
    }
    printf("\n%d %d", sum1, sum2);  // 第一个重量，第二个价值

    getch();
    return 0;
}