點擊打開鏈接

這題是一道二維費用背包問題，剛開始的時候我把所有的都初始化為-1，只有ans[0][0]=0，這樣是不對的，為什么呢。。。

如果要恰好用完的話，是要將別的都初始化為-1。但是這個恰好是指的物品的件數恰好，

那么就是說二維的費用中有一個費用是恰好，所以初始化-1的時候只要是對有這個要求的這一維進行初始化就可以了。

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int dp[1100][1100],n, m, L, v[110], t[110]; int main() {int T;scanf("%d", &T);while(T--){scanf("%d%d%d", &n, &m, &L);for(int i =0; i<n; i++){scanf("%d%d", &t[i], &v[i]);}memset(dp, -1, sizeof(dp));for(int j =0 ; j<=L; j++)dp[0][j]=0;//for(int i =0; i<1100; i++)//for(int j =0; j<1100; j++)//dp[i][j]=-1e9;for(int i =0; i<n; i++){for(int j =m; j>=1; j--)for(int p =L; p>=t[i]; p--){if(dp[j-1][p-t[i]]!=-1&&(dp[j-1][p-t[i]]+v[i])>dp[j][p])dp[j][p]=dp[j-1][p-t[i]]+v[i];}}if(dp[m][L]==-1)puts("0");elseprintf("%d\n", dp[m][L]);}return 0; }

這是不是不太理解，想一下完全背包要完全恰好要完全裝滿的話要保證dp【0】要是一零開始。

總結

以上是生活随笔為你收集整理的HU 3496 Watch The Movie---二维费用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。