暗暗的胡同 2021-11-11 10:32 采纳率: 80%
浏览 77
已结题

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

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

img

  • 写回答

2条回答 默认 最新

  • 广大菜鸟 2021-11-11 11:19
    关注

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

    //一维数组解法
    #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
    */
     
    
    

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
  • been_ss 2021-11-11 11:17
    关注

    哈喽,看看这个,有用请点采纳

    /*背包问题:
    背包所能容纳重量为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;
    }
    
    
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 11月19日
  • 已采纳回答 11月11日
  • 创建了问题 11月11日

悬赏问题

  • ¥15 爬虫爬取安居客新房信息
  • ¥15 php5.3内存泄露
  • ¥15 DigSilent如何复制复合模型到自己案例?
  • ¥15 求日版华为b610s-77a 官方公版固件,有偿
  • ¥15 关于#java#的问题,请各位专家解答!(相关搜索:java程序)
  • ¥15 linux tsi721的驱动编译后 insmod 提示 报错
  • ¥20 multisim测数据
  • ¥15 求无向连通网的所有不同构的最小生成树
  • ¥15 模拟器的framebuffer问题
  • ¥15 opencv检测轮廓问题