密码忘了

用户名：forgotpswd

访问量：3803

签　名：

听取WA声一片

等　　级
排　　名	1392
经　　验	2922
参赛次数	8
文章发表	3
年　　龄	0
在职情况	学生
学　　校	HNU
专　　业	CS

　　自我简介：

我作为一个若者，还是需要多吸取一些人生经验。

TA的其他文章

【排队买票】（C++代码）【卡特兰数】【反向求解】
浏览：1684

小O的溢出-题解(C++代码)
浏览：1149

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （C++代码）按照惯例的只有一行核心代码

小O的溢出-题解(C++代码)

　　作者: 密码忘了　　　　发表时间：2019-12-27 13:33:32 浏览：1149　|　评论：0　

原题链接：小O的溢出

## 题目：
除了学习C语言外,小O同样喜欢各种游戏,最近小O沉迷于
一款卡牌游戏不能自拔,小O希望在游戏中获得更高的排名
游戏的排名是根据获得的point的数量来计算的,获得point的
方法是用手中的卡牌去挑战BOSS,造成的伤害点数就是能获得的
point,point越高则排名越高,小O当然希望自己排名越高越好了
但是他不知道怎么使用手中的卡牌能获得更多的点数,
不过他知道聪明的你能帮他解决这个问题,所以来找你帮忙了
为了简化问题,我们假定小O手中拥有n张卡牌,
每张卡牌有一个攻击力a[i],BOSS的血量为m点
每张卡牌最多可以使用一次(可以不用,顺序随意),
当BOSS的血量少于等于0时,不能再攻击
因为point点数是根据伤害计算的,
所以最后一击的攻击力会被全部计入伤害中

## 分析：
这是一道 0-1 背包的拓展问题，与常规 0-1 背包不同的是，“撑破背包的最后一件物品”可以带走。将问题转化为 0-1 背包的表述就是：
>已知背包容量 V 和每件物品的体积，且：
- 若背包未满，则无论当前物品是否超过剩余容量，总可以装进去。
- 若背包已满或者已过载，则不能再放入物品。

>问最多能带走多少体积的物品。

## 解法：
1. 先将最大件挑出，用其余物品尽可能地装满 V-1 的空间。
（记此时背包内物品总体积为 S）
2. 最后将最大件装入背包。
（记此时背包内物品总体积为 S'）

### 证明：

记最大的物品为 m：

- 若装入最后一件物品前，背包内未放入 m：
根据定义，此时背包内物品总体积 R 总是小于等于 S，而为了获得当前最优解，最后一件物品应当放入最大的 m，故当前情况的最优解 R + m 总是小于等于 S' = S + m。

- 若装入最后一件物品前，背包内已放入 m：
此时，为了获得当前最优解，必然要找到剩余物品中最大的一件：记为 m'。故当前最优解为 R + m'。由于 R 是未装满状态，m > m'，故 R - m + m' 也是未装满状态，且未放入 m；于是有 R - m + m' <= S，从而 R + m' <= S'。

于是证明 S' 是整体的最优解。

### 实现代码
```cpp
#include<iostream>
#include<vector>
using namespace std;

int dp[101][10000] = { 0 };

int bigger(int i, int j)
{
    return i > j ? i : j;
}

int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        vector<int> v;
        int max;
        cin >> max;
        int temp;
        for (int i = 1; i < n; i++)
        {
            cin >> temp;//抽出最大值，其余压入容器
            if (temp > max)
            {
                v.push_back(max);
                max = temp;
            }
            else
                v.push_back(temp);
        }
        vector<int>::iterator it = v.begin();
        int item1 = *it;
        for (int i = 1; i < m; i++)//初始化 dp 数组第一行
        {
            if (i >= item1)
                dp[1][i] = item1;
            else
                dp[1][i] = 0;
        }
        it++;
        for (int i = 2; i < n; i++, it++)//递推计算 V-1 背包的最优解
        {
            int item = *it;
            for (int j = 1; j < m; j++)
            {
                if (j < item)
                {
                    dp[i][j] = dp[i - 1][j];
                }
                else
                {
                    dp[i][j] = bigger(dp[i - 1][j], dp[i - 1][j - item] + item);
                }
            }
        }
        cout << dp[n - 1][m - 1] + max << endl;
    }
    return 0;
}

```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

密码忘了

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C++代码）按照惯例的只有一行核心代码

【出圈】（C语言代码）用单项循环链表

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

小O的溢出-题解(C++代码)

评论区

精彩推荐

C语言训练-排序问题<2> （C++代码）（sort函数）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言训练-斐波纳契数列（C语言代码）

妹子杀手的故事（C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

【亲和数】（C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

密码忘了

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C++代码）按照惯例的只有一行核心代码

【出圈】 （C语言代码）用单项循环链表

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

小O的溢出-题解(C++代码)

评论区

精彩推荐

C语言训练-排序问题<2> （C++代码）（sort函数）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

妹子杀手的故事 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

【亲和数】 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

【出圈】（C语言代码）用单项循环链表

　　评论区

C语言训练-斐波纳契数列（C语言代码）

妹子杀手的故事（C语言代码）

【亲和数】（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）