大家好，又见面了，我是你们的朋友全栈君。
/*背包问题: 背包所能容纳重量为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; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/154547.html原文链接：https://javaforall.net
