昨日はじめてナップザック問題解いたので今度はこれをDP。解けた嬉しい。
ちょっと悪問てか、勝手に解釈して勝手に最も適切に解いたつもりだったんだけどWAでイラっとした。
例えばそば粉1100g買う場合に、そのまま1100gだけ買おうとすると
B店 300g*2袋(1100円) + C店 500g*1袋(550円)で1950円かかる。
んだけども そば粉1200g買う場合には、
B店 300*4袋(割引後価格1870円) = 1870円 で買える。
こっちの方が量多いわ安いわで、お買い得。
でそれを考慮したのがコメントアウト部分だったんですが、それをするとWAだったので泣きました。
#include <iostream> #include <vector> using namespace std; #define MAXVALUE (1<<21) vector<int> dp(5000+1,MAXVALUE); void init(){ int item[6] = {200,300,500,1000,1200,1500}; int price[6]= {380,550,850,1520,1870,2244}; dp[0]=0; for(int k=0;k<6;k++){ for(int i=0;i+item[k]<=5000;i++){ dp[i+item[k]] = min( dp[i+item[k]] , dp[i]+price[k] ); } } } int main(){ init(); int n,mi; while(cin >> n && n){ mi = dp[n]; /*for(int i=n;i<=5000;i++){ mi = min(dp[i],mi); }*/ cout << mi << endl; } }