---
title: "整数拆分"
created: 2025-11-28
tags:
  - 算法
---

# 整数拆分

## 题目 [整数拆分](https://www.acwing.com/problem/content/description/3385/)

![[image-9e3dd3b7.png]]

## 思路分析

和上题基本一样 这次多了一个限制 不是由1-n-1的物品中选了 而是只在n的范围内的2^k中选

所以得先把物品处理出来

`int cnt=1;`

`for(int i=1;i<=m;i*=2)`

`v[cnt++]=i;`

`n=cnt-1;`

比如4 可以分为1111 112 22 4 在4的范围下只能有3个物品选

第1个物品为2^0=1 第2个物品为2^1=2 第3个物品为2^2=4

n表示物品总数 因为cnt是从1开始的 所以物品数量应该是cnt-1（第3个物品存进去后 cnt又++了一次）

物品处理出来了 n个物品 总价值不超过m 每个物品可多选 所以又是一个完全背包问题

（直接画优化后的图了 优化后其实就是一个反过来的01背包 所以也就是选与不选两种）

![[image-6be48eb1.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e6+10,mod=1e9;

LL v[N],dp[N];

int n,m;

int main()

{

    cin>>m;

    int cnt=1;

    for(int i=1;i<=m;i*=2)

        v[cnt++]=i;

    n=cnt-1;

    dp[0]=1;

    for(int i=1;i<=n;i++){

        for(int j=v[i];j<=m;j++){

            dp[j]=(dp[j]+dp[j-v[i]])%mod;

        }

    }

    cout<<dp[m];

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[完全背包练习|完全背包练习]] 🏠 [[00-刷题理模型]] ➡️ [[自然数拆分|自然数拆分]]