积分商城

最新搜索： GJB548B kingst 三星 逻辑板 esp32指令集 双飞翼 电动车充电器电路图
您现在的位置是：首页 > 笔记 > 背包问题的变体：恰好装满 求方案数与求最优解.docx
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

背包问题的变体：恰好装满 求方案数与求最优解.docx

更新时间：2026-10-10 20:46:05 大小：39K 上传用户：江岚查看TA发布的资源 标签：-1 knapsackexact fillnumber of solutionsoptimal solutiondynamic programming 下载积分：2分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

背包问题的变体：恰好装满、求方案数与求最优解

一、背包问题的三种常见变体

标准的0-1背包求"最大价值"，但在实际应用中还有其他变体：

1. 恰好装满背包：求恰好填满容量时的最大价值

2. 求方案数：计算有多少种方式填满背包

3. 求具体方案：还原最优解对应的物品选择

二、恰好装满的背包

2.1 问题描述

0-1背包中，不要求恰好装满，允许有剩余容量。但某些问题（如装箱、恰好凑钱）要求恰好装满。

2.2 实现

只需修改初始化方式：dp[0] = 0，其余初始化为负无穷（表示不可达状态）。

#define NEG_INF -1000000

int knapsackExact(int n, int W, int *weight, int *value) {
    int dp[W + 1];
    for (int j = 1; j <= W; j++) {
        dp[j] = NEG_INF;   // 不可达状态
    }
    dp[0] = 0;   // 容量0恰好装满，价值为0
    
    for (int i = 1; i <= n; i++) {
        for (int j = W; j >= weight[i]; j--) {
            if (dp[j - weight[i]] != NEG_INF) {
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            }


部分文件列表

文件名 大小
背包问题的变体：恰好装满、求方案数与求最优解.docx 39K

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号