做亚马逊联盟一定要有网站吗/热搜榜上2023年热门话题

这种题目一开始是用二维数组写的，但是会超时。

后面用一维数组是因为恰巧信息的流动都是至右向左，所以可以覆盖掉d[j].但是如果换个思维，视j为背包的空余，那么方向就相反了，就不能用一位数组了。

#include <iostream>
#include <bits/stdc++.h>#define maxn 3450
#define INF 0x3f3f3f3f
using namespace std;
int w[maxn], c[maxn];long long d[12890];//int main() {
//    int N,M;
//    while (cin>>N>>M){
//        for(int i = 1;i<=N;i++){
//            cin>>w[i]>>c[i];
//        }
//        memset(d,-INF, sizeof(d));
//        //init
//        for(int i = 0;i<=M;i++){
//            d[N+1][i] = 0;
//            d[N][i] = 0;
//        }
//
//        for(int i = N;i>=1;i--){
//            for(int j = 0;j<=M;j++){
//                if(j>=w[i]){
//                    d[i][j] = max(d[i+1][j],d[i+1][j-w[i]]+c[i]);
//                }
//            }
//        }
//
//        cout<<d[1][M]<<endl;
//    }
//
//    return 0;
//}int main() {int N, M;while (cin >> N >> M && N &&M) {for (int i = 1; i <= N; i++) {cin >> w[i] >> c[i];}memset(d, -INF, sizeof(d));for(int i = 0;i<=M;i++){d[i] = 0;}for(int i = 1;i<=N;i++){for(int j =M;j>=0;j--){if(j>=w[i]){d[j] = max(d[j],d[j-w[i]]+c[i]);}}}cout<<d[M]<<endl;}return 0;}