动态规划——背包问题(c语言)

动态规划——背包问题(c语言)/*背包问题:背包所能容纳重量为10;共五件商品,商品重量用数组m存储m[5]={2,2,6,5,4},每件商品的价值用数组n存储,n[5]={6,3,5,4,6};求背包所能装物品的最大价值。

大家好,又见面了,我是你们的朋友全栈君。

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

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/154547.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号