动态规划背包问题c++

img

img


想问一下让能量花价值-b[i]的代码应该放在哪里以及还有没有其他错误

先找到能量最多的那一朵花，收集它的能量，然后让能量花价值-b[i]，重新找到能量最多的那一朵……
依次循环，直到采收了m次
参考代码：


#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,a[105],b[105],maxn,s=0;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    for(int i=0;i<m;i++){
        maxn=0;
        for(int j=0;j<n;j++)
            if(a[j]>a[maxn])
                maxn=j;
        s+=a[maxn];
        a[maxn]-=b[maxn];
    }
    cout<<s;
    return 0;
}

这个题，我以为是混合背包问题，后面觉得是用分组背包问题。意思是：同种花是一组，区别是能拿多少，0-maxTime之间都是组内不同情况，根据背包问题模板修改下，我的建议如下：（提供其他测试数据或网站url试试）


#include<iostream>
#include<algorithm>
#define MAXSIZE 10
using namespace std;

int dp[MAXSIZE];
int a[MAXSIZE]; 
int b[MAXSIZE]; 
int w[MAXSIZE]; 

int main() {
    int n, m;
    //n:n个花，最多m次
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    //种类
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        int maxTime = m;
        if (b[i] > 0) {
            int k=1;
            for (; a[i] > k * b[i]; k++) {
                w[k] = w[k - 1] + a[i] - (k - 1) * b[i];
            } 
            maxTime = min(maxTime, k-1);
        }
        else {
            for (int k = 1; k<=m; k++) {
                w[k] = k * a[i];
            }
        }
        //数量 
        for (int j = m; j >= 0; j--) {
            //顺序遍历组内的组合 0,1,2,3,...
            for (int k = 0; k<= maxTime; k++) {
                if (j >= k) {
                    dp[j] = max(dp[j], dp[j - k] + w[k]);
                }
            }
        }
    }
    cout << dp[m] << endl;
}
/*
3 3
10 20 30
0 5 20

一：30 
10    20    10  
0    5    20

二：20

10    15    10
0    5    20

三：15
10    10    10
0    5    20

30 + 20 + 15 = 65 
*/

img